How to get every possible pattern of an array of letters [duplicate]

Question

Possible Duplicate:
Are there any better methods to do permutation of string?

Lets say I have the letters

a b c d

and I want to get every single possible pattern/combination of these letters in a string that is 4 letters long.

aaaa

baaa

caaa

daaa

abaa

acaa

acad

abba

and so on.

What loop or pattern can I use to list every combination possible?

I am writing this in C#, but examples in C++ and javascript are welcome as well.

My current idea only increments one letter for each letter possible. Then shifts to the right once and repeats. This doesn't cover patterns like.

abba

Answer 1

You can do so very easily with LINQ:

string[] items = {"a", "b", "c", "d"};
var query = from i1 in items
            from i2 in items
            from i3 in items
            from i4 in items
            select i1 + i2 + i3 + i4;

foreach(var result in query)
    Console.WriteLine(result);

If you don't know ahead of time that you want the combinations of four, you can compute arbitrary Cartesian Products with a bit more work:

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

Answer 2

Here's one with only one for loop

var one = ['a','b','c','d'];
var length = one.length;
var total = Math.pow(length, length);
var pow3 = Math.pow(length,3);
var pow2 = Math.pow(length,2);

for(var i = 0; i<total; i++)
    console.log(one[Math.floor(i/pow3)], 
        one[Math.floor(i/pow2)%length], 
        one[Math.floor(i/length)%length], 
        one[i%length]);

---

Here's a simple inefficient method:

var one = ['a','b','c','d'];
var i,j,k,l;
var len = 4;
for(i=0;i<len;i++) {
    for(j=0;j<len;j++) {
        for(k = 0; k < len; k++) {
            for(l = 0; l<len; l++) {
                console.log(one[i], one[j], one[k], one[l]);
            }
        }
    }
}

Similar C#:

        var one = new[] {'a','b','c','d'};
        var len = one.Length;

        for(var i=0;i<len;i++) {
            for(var j=0;j<len;j++) {
                for(var k = 0; k < len; k++) {
                    for(var l = 0; l<len; l++) {
                        Console.Write(one[i] +  one[j] + one[k] +  one[l]);
                    }
                }
            }
        }

Answer 3

Just for the heck of it, here's a generic solution for any number of letters in javascript.

http://jsfiddle.net/U9ZkX/

Interestingly, google chrome would like to translate the output from "Malay".

var letters = ['a', 'b', 'c', 'd'];
var letterCount = letters.length;
var iterations = Math.pow(letterCount, letterCount);

for (var i = 0; i < iterations; i++) {
    var word = "";

    for (var j = 0; j < letterCount; j++) {
        word += letters[Math.floor(i / Math.pow(letterCount, j)) % letterCount];
    }

    document.write(word + "<br>");
}

Answer 4

A recursive C# implementation:

public IEnumerable<string> CreateCombinations(IEnumerable<char> input, int length)
{
    foreach (var c in input)
    {
        if (length == 1)
            yield return c.ToString();
        else 
        {
            foreach (var s in CreateCombinations(input, length - 1))
                yield return c.ToString() + s;
        }
    }
}

Should allow for any number of characters and any required string length (well until the stack overflows :))

Using it:

foreach (var s in CreateCombinations("abcd", 4))
{
    Console.WriteLine(s);
}

Results in:

aaaa
aaab
aaac
aaad
aaba
aabb
aabc
aabd
aaca
...
dddd

Answer 5

I came to this javascript solution using recursion. anyway not really expensive with these constraints (only 4^4 calls)

(function() {
   var combinations = [];

   (function r(s) {
       s = s || '';
       if (s.length === 4) {
          combinations[combinations.length] = s;
          return;
       }
       r(s + 'a');
       r(s + 'b');
       r(s + 'c');
       r(s + 'd');

   })();

   console.log(combinations);
})();

The output is

["aaaa", "aaab", "aaac", "aaad",...., "dddc", "dddd"]