CODEWITHSUNDEEP
algorithmpermutationdiscrete-mathematicslexicographic
maciek
maciek

Reputation: 2117

Generating all lexicographical permutations without comparisons of elements

I came into the problem when I have a given sequence s=(a,b,c,d,e...) - sorted in non-decreasing order. My job is to develop an algorithm that is going to generate all possible permutations in lexicographical order - ending on the reversed s (highest in order).

The trick is: I cannot compare any 2 element to each other. All operations must be done "automatically", regardless of elements values.

Upvotes: 2

Views: 1201

Answers (1)

kraskevich
kraskevich

Reputation: 18566

You can do it this way:

// n is the number of elements in the given sequence
p = all permutations of [0, 1, ..., n - 1] in lexicographical order    
for permutation in p:  
        for i = 0 ... n - 1
            print(s[permutation[i]]) // s is the given sequence

You can generate all permutations of [0, 1, ..., n - 1] using any standard algorithm(recursively or starting with {0, 1, ..., n - 1} and generating the next permutation n! - 1 times). Actually, a standard recursive algorithm for generating all permutations applied directly to the given sequence will generate them in right order(and it does not require comparing elements).

Here is pseudo code of recursive algorithm:

// Generates all permutations recursively
// permutation - a prefix of an arbitrary permutation
// sequence - the input sequence
// used - a boolean array where used[i] = true if and only if
// an element with index i is already in permutation
def generatePermutations(permutation, sequence, used)
    if permutation.length() == sequence.length()
        // The permutation is fully generated
        print(permutation)
    else
        // Adds all elements that are not present in permutation yet.
        // Starts with the smallest index to maintain the correct order.
        for i = 0 ... sequence.length() - 1
            if not used[i]
                used[i] = true
                permutation.push_back(sequence[i])
                generatePermutations(permutation, sequence, used)
                used[i] = false
                permutation.pop_back()

sequence = input()
permutation = an empty list
used = array of sequence.length() elements filled with a
generatePermutations(permutation, sequence, used)

Upvotes: 1

Related Questions