permutations/variation

Question

I am trying to come up with a C# method that will be able to generate permutations plus variations. I think it is best explained in an example. I am spacing on the best way to accomplish this. This is how I am thinking about it in my head.

I am looking for suggestions on how to approach this, maybe pseudo code?

ABC becomes

Step 1) permutation without repetition:

ABC
ACB
BAC
BCA
CAB
CBA

Step 2) variation with |

ABC
  A|BC
  AB|C

ACB
  A|CB
  AC|B

BAC
  B|AC
  BA|C

BCA
  B|CA
  BC|A

CAB
  C|AB
  CA|B

CBA
  C|BA
  CB|A

So you end up with a final set of

  A|BC
  AB|C
  A|CB
  AC|B
  B|AC
  BA|C
  B|CA
  BC|A
  C|AB
  CA|B
  C|BA
  CB|A

Update: Just a quick implementation i wrote up, i know it's horrible, any comments welcome.

        var perms = Permuter.Permute(new Char[] {'a', 'b', 'c'}).ToList();
        DisplayResult(perms);

        foreach (var permutation in perms.ToList())
        {
            var p = permutation.ToList();

            int splitPos = 1;
            do
            {
                for (int i = 0; i < splitPos; i++)
                {
                    Console.Write(p[i]);
                }

                Console.Write("|");

                for (int j = splitPos; j < p.Count; j++)
                {
                    Console.Write(p[j]);
                }

                Console.WriteLine("");
                splitPos++;
            } while (splitPos < p.Count);
        }

Answer 1

looking for educational purposes, just getting interesting in permtations and sets and things, trying to understand how to put these things together.

There are lots of different ways to do permutations, and lots of them are edifying. Here's one sketch to get you thinking.

Consider restricting the problem to finding all permutations of a subset of the set of integers from 0 to 31. So you might choose as your set { 2, 3, 5 } and generate the permutations (2, 3, 5), (2, 5, 3), (3, 2, 5), (3, 5, 2), (5, 2, 3) and (5, 3, 2). How to do that?

Define an immutable struct that contains a single 32 bit integer. Make the struct implement IEnumerable<int> and have it enumerate the numbers corresponding to all the bits that are set in it. Also make a method "Remove" that gives you back a different struct with the given bit removed.

Now you can make a recursive algorithm like this:

• Is the set empty? Then there is one permutation, the empty sequence.

• Is the set not empty? Then for each item in the set: make the set that is the original set without that the item, recursively make all the sequences from the smaller set, and append the item to each of those sequences.

That is, again, suppose the set is {2, 3, 5}. What do you do? For each item 2, 3, 5:

Remove the item 2. That leaves 3 and 5. Permute 3, 5. How?
    Remove item 3. That leaves 5. Permute that.
        Remove item 5. That leaves nothing. Permute that.
            The result is the empty sequence.
        Append 5 to the empty sequence. That's (5).
    Append 3. That's (5, 3).
    Remove 5. That leaves 3. Permute that.
        Remove 3. That leaves nothing. Permute that.
            The result is the empty sequence.
        Append 3 to the empty sequence. That's (3).
    Append 5. That's (3, 5).
Append 2 to each of those results. That's (2, 5, 3) and (2, 3, 5).
Remove 3. That leaves 2 and 5. Permute that....

Turning that into code will be a bit tricky but quite edifying.

Answer 2

First, generate the permutations. Lexicographic ordering is the simplest to implement; see Wikipedia and Knuth's The Art of Computer Programming. Here's one implementation in Python (source):

def permutations_of( seq ):
    yield seq
    seqlen = len(seq)
    while True:
        j = seqlen - 2
        while j >= 0 and seq[j] >= seq[j+1]:
            j -= 1

        if j < 0: break

        i= seqlen - 1
        while i > j and seq[i] < seq[j]:
            i -= 1

        seq[j],seq[i] = seq[i],seq[j]
        seq[j+1:] = seq[-1:j:-1]
        yield seq

You could also use the Steinhaus–Johnson–Trotter algorithm, which is a bit faster.

To generate the variations, loop through your strings, and for each possible position within the string, insert | in that position.