Getting all the permutations in an array

Question

Hi, say i have the following array:

string[] = new string[] { "A", "B", "C" };

How can i produce all the possible permutations which contains only 2 characters and no two the same (eg AB would be the same as BA). Therefore using the above array it would produce:

AB
AC
BC

Please note that this example has been simplified therefore the array and the length of the string required will be greater.

I'd really appreciate if someone could help.

Answer 1

Lets extend it, so maybe we can see the pattern:

string[] arr = new string[] { "A", "B", "C", "D", "E" };

//arr[0] + arr[1] = AB
//arr[0] + arr[2] = AC
//arr[0] + arr[3] = AD
//arr[0] + arr[4] = AE

//arr[1] + arr[2] = BC
//arr[1] + arr[3] = BD
//arr[1] + arr[4] = BE

//arr[2] + arr[3] = CD
//arr[2] + arr[4] = CE

//arr[3] + arr[4] = DE

I see two loops here.

• The first (outer) loop goes from 0 to 3 (arr.Length - 1)
• The second (inner) loop goes from the outer loops counter + 1 to 4 (arr.Length)

Now it should be easy to translate that to code!

Answer 2

These should give you a starting point:
http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate
http://www.codeproject.com/KB/recipes/Combinatorics.aspx

Answer 3

Since ordering does not matter, these are actually combinations and not permutations. In any case, there is some sample code here (you want the section entitled "Combinations (i.e., without Repetition)".

Answer 4

What you are looking for is an double Loop along the lines of the following pseudo code.

for(int i = FirstElement;i<= LastElement; increment i)
{
for(j = i;j<= lastElement; increment j)
{
if(i!= j)
{
print (i,j)
}
}
}

Answer 5

public string[] Permute(char[] characters)
{
    List<string> strings = new List<string>();
    for (int i = 0; i < characters.Length; i++)
    {
        for (int j = i + 1; j < characters.Length; j++)
        {
            strings.Add(new String(new char[] { characters[i], characters[j] }));
        }
    }

    return strings.ToArray();
}

Answer 6

It's the sum of 1 to n-1 or n(n-1) / 2.

int num = n * ( n - 1 ) / 2;

Obviously you could generalize the n * ( n - 1 ) using a pair of factorials for whatever you are trying to do (string size wise).

Answer 7

What you're asking for are combinations, not permutations (the latter term implies that order matters). Anyway, it's a classic use for recursion. In pseudo-code:

def combs(thearray, arraylen, currentindex, comblen):
  # none if there aren't at least comblen items left,
  # or comblen has gone <= 0
  if comblen > arraylen - currentindex or comblen <= 0:
    return
  # just 1 if there exactly comblen items left
  if comblen == arraylen - currentindex:
    yield thearray[currentindex:]
    return
  # else, all combs with the current item...:
  for acomb in combs(thearray, arraylen, currentindex+1, comblen-1):
    yield thearray[currentindex] + acomb
  # ...plus all combs without it:
  for acomb in combs(thearray, arraylen, currentindex+1, comblen):
    yield acomb

Answer 8

Didn't tested and not the fastest, but:

IEnumerable<String> Combine(String text, IEnumerable<String> strings)
{
    return strings.Select(s => text + s).Concat(Combine(strins.Take(1).First(), strings.Skip(1))
}

Call:

foreach (var s in Combine("" , arrayOfStrings))
{
     // print s
}