Generating all permutations of pairs excluding permutations of individual elements

Question

I would like to generate all permutations of the ordered pairs (a, b) where a != b, and a, b are elements of set S (let's say S := {1..k}), but excluding permutations of the individual elements of S.

For example, setting k = 2, the possible ordered pairs are (1, 2), (2, 1) giving 2 possible sequences:

• (1, 2), (2, 1)
• (2, 1), (1, 2)

but which are actually duplicates under the permutation mapping of {1->2, 2->1}.

For k = 3, there would be 6 possible ordered pairs, giving 6! sequences (including duplicates). But with 3! = k possible permutations, the desired number of unique sequences is 5!, and is easily generated by only taking sequences that begin with the pair (1, 2).

In the general case, there would be k*(k-1) pairs, giving [k * (k-1)]! sequences (including duplicates), and there would be k! permutations, so I should end up with [k * (k-1)]! / k! sequences.

I only intend to use small values of k, but am wondering if there are any good ways of generating these sequences. I'm fairly certain this is a specific case of filtering out unique sequences [allowing duplicate elements] subject to permutations of the possible elements in those sequences, but maybe there's something particular about what I'm looking for that is easier than the brute-force approach of generating all possible sequences and then filtering.

Answer 1

I think you can extend your approach of only generating sequences that start with (1,2) to only generate sequences that if you consider each digit in turn then either:

1. the digit matches a previous digit
2. the digit is the next unseen digit

So a sequence like (1,2)(2,1) and (1,2)(3,4) would be allowed, but not (1,2)(4,5) because the 4 violates the rules (3 is the next unseen digit at this stage).

Given this you can then generate all the combinations recursively by choosing each pair in turn, where each pair must be both a new pair, and satisfy the rules.

e.g. for k=3

(1,2) Only option for level 1
(1,2) can be followed by (2,1) or (1,3) or (2,3) or (3,1) or (3,2)
(1,2)(2,1) can be followed by (3,1) or (3,2) or (1,3) or (2,3)
(1,2)(2,1)(3,1) can be followed by...

Answer 2

Take a look at backtraking algorithm:

http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html

Generating permutations is an NPC problem so all solutions will have an exponential complexity.