CODEWITHSUNDEEP
algorithmpermutationenumerationcombinatoricsbacktracking
bacon_is_good
bacon_is_good

Reputation: 53

Efficiently generate permutations with ordering restrictions(possibly without backtracking)?

I need to generate permutations of with ordering restrictions on ordering

for example, in the list [A,B,C,D]

A must always come before B, and C must always come before D. There also may or may not be E,F,G... that has no restrictions. The input would look like this: [[A,B],[C,D],[E],[F]]

Is there a way to do this without computing unnecessary permutations or backtracking?

Upvotes: 2

Views: 275

Answers (1)

tobias_k
tobias_k

Reputation: 82899

Normally, a permutations algorithm might look somewhat like this (Python):

def permutations(elements):
    if elements:
        for i, current in enumerate(elements):
            front, back = elements[:i], elements[i+1:]
            for perm in permutations(front + back):
                yield [current] + perm
    else:
        yield []

You iterate the list, taking each of the elements as the first element, and combining them with all the permutations of the remaining elements. You can easily modify this so that the elements are actually lists of elements, and instead of just using the current element, you pop the first element off that list and insert the rest back into the recursive call:

def ordered_permutations(elements):
    if elements:
        for i, current in enumerate(elements):
            front, back = elements[:i], elements[i+1:]
            first, rest = current[0], current[1:]
            for perm in ordered_permutations(front + ([rest] if rest else []) + back):
                yield [first] + perm
    else:
        yield []

Results for ordered_permutations([['A', 'B'], ['C', 'D'], ['E'], ['F']]):

['A', 'B', 'C', 'D', 'E', 'F']
['A', 'B', 'C', 'D', 'F', 'E']
['A', 'B', 'C', 'E', 'D', 'F']
[ ... some 173 more ... ]
['F', 'E', 'A', 'C', 'D', 'B']
['F', 'E', 'C', 'A', 'B', 'D']
['F', 'E', 'C', 'A', 'D', 'B']
['F', 'E', 'C', 'D', 'A', 'B']

Note, though, that this will create a lot of intermediate lists in each recursive call. Instead, you could use stacks, popping the first element off the stack and putting it back on after the recursive calls.

def ordered_permutations_stack(elements):
    if any(elements):
        for current in elements:
            if current:
                first = current.pop()
                for perm in ordered_permutations_stack(elements):
                    yield [first] + perm
                current.append(first)
    else:
        yield []

The code might be a bit easier to grasp, too. In this case, you have to reserve the sublists, i.e. call it as ordered_permutations_stack([['B', 'A'], ['D', 'C'], ['E'], ['F']])

Upvotes: 3

Related Questions