-1
$\begingroup$

I'm trying to find away to iterate through all permutations of the set: $$S_n=\{a_1, a_1, a_2, a_2, ..., a_n, a_n\}$$ A set of $n$ distinct elements and 2 of each element. The catch is that for any $i$ and $j$, exchanging all $a_i$ and $a_j$ does NOT create a new permutation. Ex. $$(1,1,2,2)=(2,2,1,1)$$ $$(1,2,3,1,2,3)=(3,1,2,3,2,1)$$ To be clear, here are the sets for $n=2$ and $n=3$ , respectively, found by hand: $$(1,1,2,2),(1,2,1,2),(1,2,2,1)$$ $$(1,1,2,2,3,3),(1,1,2,3,2,3),(1,1,2,3,3,2),(1,2,1,2,3,3),(1,2,1,3,2,3),(1,2,1,3,3,2),(1,2,2,1,3,3),(1,2,3,1,2,3),(1,2,3,1,3,2),(1,2,2,3,1,3),(1,2,3,2,1,3),(1,2,3,3,1,2),(1,2,2,3,3,1),(1,2,3,2,3,1),(1,2,3,3,2,1)$$ Perhaps some kind of recursive function would work.

$\endgroup$
0
$\begingroup$

The obvious recursive function simply enforces that the first appearance of each element is in lexicographic order. Here's some Java code which counts the permutations by generating them, and can be adapted to print them:

public class Maths1987783 {
        public static void main(String[] args) {
                for (int n = 1; n < 8; n++) {
                        int[] a = new int[n];
                        for (int i = 0; i < a.length; i++) a[i] = 2;
                        System.out.println(count(0, a));
                }
        }

        private static long count(int max, int[] remaining) {
                long accum = 0;
                boolean empty = true;
                for (int i = 0; i <= max && i < remaining.length; i++) {
                        if (remaining[i] > 0) {
                                remaining[i]--;
                                accum += count(i == max ? max+1 : max, remaining);
                                remaining[i]++;
                                empty = false;
                        }
                }

                return empty ? 1 : accum;
        }
}

That gives enough of a clue to find OEIS A001147, whose many comments suggest alternative generation approaches. For example:

a(n) is also the number of perfect matchings in the complete graph K(2n). - Ola Veshta

Which is obvious in retrospect: label the vertices $1$ to $2n$, and each edge in the matching means that those two positions have equal elements. You may well be able to find existing routines to iterate through perfect matchings of a complete graph.

There are a couple of references to counting certain classes of trees which might have useful bijections, although I haven't found them in a couple of minutes' thought.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.