Geek asks and answers

Generation of all permutations of pairs, excluding permutations of individual elements

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

For example, when setting k = 2, possible ordered pairs: (1, 2), (2, 1) give two possible sequences:

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

but which are actually duplicated when displaying permutations {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 required number of unique sequences is 5!, And is easily generated only by taking sequences starting with a pair (1, 2).

In the general case, there would be k * (k-1) pairs giving [k * (k-1)]! sequences (including duplicates), and there will be k! permutations, so I have to finish using [k * (k-1)]! / k! sequence.

I only intend to use small k values, but I wonder if there are good ways to generate these sequences. I am pretty sure that this is a specific case of filtering unique sequences [allowing duplicate elements] to obey permutations of possible elements in these sequences, but maybe there is something special in what I'm looking for, which is simpler than rough - a force approach for creating all possible sequences and then filtering.

+3
source share
2 answers

, , (1,2), , , , :

  • -

, , (1,2) (2,1) (1,2) (3,4), (1,2) (4,5), 4 (3 - ).

, , , , .

. 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...
+1

More articles:


All Articles