CODEWITHSUNDEEP
algorithmpermutationcombinatoricscircular-permutations
Paul Richards
Paul Richards

Reputation: 1207

Seating problem - not generating duplicates

I want to write an algorithm to generate all the possible unique permutations that n groups of m people can sit around a circular dining table with mn seats. An arrangement of diners simply considers the group membership, and doesn't identify individuals within a group. Any two arrangements are considered identical under reflection or rotation.

For example, this is an arrangement with n=4 and m=3 (edited since there are 4 groups of 3 people). I have shown it in a square, but the geometry is irrelevant.

0 1 2 0
1     3
2     1
3 2 3 0

The following arrangements are considered identical to the above:

1 2 0 3        0 2 1 0        2 3 2 3
0     1        3     1        1     0 
1     0        1     2        0     1 
2 3 2 3        0 3 2 3        1 2 0 3

The strategy I have adopted first is an iterative depth-first search. I store the candidates in a stack, where each candidate is an array of integers. At each iteration I add whichever integers to each candidate array are within the rules. If the required array length is reached then I pop the completed arrangement off the stack and store it in a list. Otherwise I add it back to the stack for further consideration.

The above generates a lot of duplicates. For example, these are all equivalent:

Then, I remove duplicates from the list of arrays generated by the above process. To do this I compare arrays to take into account rotation (by pairwise comparison using an increasing offset) and reflection. This is time-consuming.

EDIT: Important constraint missed: no two adjacent people may be from the same group.

My question is this: how can I speed up the above by avoiding duplicates during the generation process? One partial answer is to start by fixing the first element in the array, i.e. insisting that it starts with a zero, since any arrangement can be rotated to have the group signified by zero in a particular position. This is an improvement as it would generate only 6 arrangements in the above case, rather than the whole 24. But, can I do better?

Upvotes: 2

Views: 91

Answers (1)

Stef
Stef

Reputation: 15515

Instead of comparing all pairs of arrangements to check whether there is a duplicate in the pair, you can map each arrangement to a canonical representative of all duplicates of this arrangement, and reject every arrangement that is not canonical.

If the arrangements have length m*n, but you have N arrangements with duplicates, where m*n is relatively small but N is huge, then comparing all pairs of arrangements would take in the order of N*N * m*n operations, whereas filtering out non-canonical arrangements necessitate only N * m*n operations.

Also, since the table is circular, you can fix an arbitrary element and consider it to always be the first element. This way, you pass one fewer element to the permutation-generating algorithm, and you immediately avoid generating a lot of duplicates.

Here I generate all seatings with more_itertools.distinct_permutations, and filter out seatings that are not lexicographically-minimal among their equivalence class of rotations and reflections.

def is_minimal(seq):
    qes = seq[::-1]
    return (
        all(seq <= qes[i:]+qes[:i] for i in range(len(seq))) and
        all(seq <= seq[i:]+seq[:i] for i in range(len(seq)))
    )

from more_itertools import distinct_permutations
from string import printable as alphabet

def seatings(n, m):
    '''all possible seatings for n groups of m people, up to reflection/rotation'''
    pool = '0' * (m-1) + alphabet[1:n] * m
    result = (''.join(('0', *seating)) for seating in distinct_permutations(pool))
    result = [seating for seating in result if is_minimal(seating)]
    return result

l42 = seatings(4, 2)

print(len(l42))
# 171

print(l42)
# ['00112233', '00112323', '00112332', '00113223', '00113232', '00113322', '00121233', '00121323', '00121332', '00122133', '00122313', '00122331', '00123123', '00123132', '00123213', '00123231', '00123312', '00123321', '00131223', '00131232', '00131322', '00132123', '00132132', '00132213', '00132231', '00132312', '00133122', '00133212', '00211233', '00211323', '00211332', '00212133', '00212313', '00213123', '00213132', '00213213', '00213312', '00221133', '00221313', '00223113', '00231123', '00231132', '00231213', '00232113', '00311223', '00312123', '00312213', '00321123', '01012233', '01012323', '01012332', '01013223', '01013232', '01013322', '01021233', '01021323', '01021332', '01022133', '01022313', '01023123', '01023132', '01023213', '01031223', '01032123', '01102233', '01102323', '01102332', '01103223', '01120233', '01120323', '01120332', '01122033', '01122303', '01123023', '01123032', '01123203', '01123302', '01130223', '01130232', '01130322', '01132023', '01132032', '01132203', '01132302', '01133022', '01133202', '01201233', '01201323', '01201332', '01202133', '01202313', '01202331', '01203123', '01203132', '01203213', '01203231', '01203312', '01203321', '01210233', '01210323', '01212033', '01212303', '01213023', '01213032', '01213203', '01213302', '01220133', '01220313', '01220331', '01221033', '01221303', '01223013', '01223031', '01223103', '01230123', '01230132', '01230213', '01230231', '01230312', '01230321', '01231023', '01231032', '01231203', '01231302', '01232013', '01232031', '01232103', '01233102', '01301322', '01302123', '01302132', '01302213', '01302231', '01302312', '01303122', '01303212', '01310223', '01310232', '01312023', '01312032', '01312203', '01312302', '01313022', '01313202', '01320132', '01320213', '01320231', '01320312', '01321203', '01321302', '01323102', '01330212', '01331022', '01331202', '02021133', '02021313', '02023113', '02031123', '02031213', '02112033', '02112303', '02113023', '02113032', '02113203', '02120313', '02121303', '02130213', '02130312', '02131203', '02203113', '02211303']

l43 = seatings(4, 3)

print(len(l43))
# 15402

print(l43)
# ['000111222333', '000111223233', '000111223323', '000111223332', '000111232233', '000111232323', '000111232332', '000111233223', '000111233232', '000111233322', ..., '022121130303', '022203031113', '022211130303']

For the record, distinct_permutations('00111222333') generates 92400 permutations, of which we keep 15402.

Upvotes: 0

Related Questions