How to get every possible pattern of an array of letters

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

@liho1eye posting two for loops is pointless since it is not the correct solution. @ james no, it can be more than 4 letters and its length can be more than 4 letters so dynamic on both parts. @ brian do you have anything better to do than search up old postings and post wikipedia links :T — John, Jan 10 '12 at 22:06
This isn't quite the same problem as permutation. Permutations of { 'a', 'b', 'c', 'd' } would not include the string "aaaa". — phoog, Jan 10 '12 at 22:07
@John - generally it's helping people with simple problems like this. I actually misread your question thinking you were looking for permutations as that's a common homework question to get posted here. I apologize - I didn't realize you were having a problem simply counting in what amounts to base4. — Brian Roach, Jan 10 '12 at 22:14
@John, do you need all of these permutations or could you simply get by with a `RegEx` to verify that the text you received is in the correct format? — , Jan 10 '12 at 22:15

score 50 · Answer 1 · edited Jan 11 '12 at 01:20

50

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

edited Jan 11 '12 at 01:20

ChrisWue

18,612
4
58
83

answered Jan 10 '12 at 22:30

Eric Lippert

647,829
179
1,238
2,067

1

I could modify in 10 secs this in order to get n combinations. This is fantastic, thanks a lot. – Leandro Bardelli Mar 08 '23 at 04:06

Joe · Answer 2 · 2012-01-10T22:27:53.353

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]);
                    }
                }
            }
        }

this could be accomplished just using one array and reference different indexes. — Brad Semrad, Jan 10 '12 at 22:06

score 3 · Answer 3 · answered Jan 10 '12 at 22:14

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>");
}

ChrisWue · Answer 4 · 2012-01-11T01:16:49.737

3

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

edited Jan 11 '12 at 01:16

answered Jan 10 '12 at 22:25

ChrisWue

18,612
4
58
83

This is the kind of answer I'd pick. It's easily parameterised over the number of sets in the Cartesian product. None of those ugly copy-and-pasted for loops. :-) – Edmund Jan 11 '12 at 19:38
This is exactly what I need. @ChrisWue - Can you help me understand what this is doing? I need the same functionality in Javascript. – jamis0n Mar 17 '14 at 03:41

score 1 · Answer 5 · answered Jan 10 '12 at 22:11

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"]

Michael · Answer 6 · 2012-01-11T03:14:48.563

1

This will probably work, too ;)

var letters = new[] {'a','b','c','d'};
Random random = new Random();
HashSet<string> results = new HashSet<string>();

while(results.Count < 256) {
    results.Add(letters[random.Next(4)] + letters[random.Next(4)]
              + letters[random.Next(4)] + letters[random.Next(4)]);
}

results.ToList().ForEach(Console.WriteLine);

edited Jan 11 '12 at 03:14

answered Jan 11 '12 at 03:04

Michael

11
2

score 1 · Answer 7 · answered Jan 11 '12 at 10:30

1

One liner in LINQ for any given n:

        var letters = new[] { "a", "b", "c", "d" };
        int n = 4;

        var z = Enumerable.Range(1, n)
            .Select(x => letters.AsEnumerable())
            .Aggregate((g,h) => g.Join(h, _ => true, _ => true, (a, b) => a + b));

answered Jan 11 '12 at 10:30

ghord

13,260
6
44
69

i edited int n = 4; to n = letters.length; – MoizNgp Apr 25 '13 at 14:04

score 1 · Answer 8 · answered Jan 12 '12 at 02:03

You have an alphabet with 2² letters, so every letter expresses exactly two bits, and thus for letters express eight bits. Now it's a simple matter of enumerating all values. In pCeudocode:

static const char alphabet[4] = { 'a', 'b', 'c', 'd' };

for (unsigned int i = 0; i != 256; ++i)
{
    for (unsigned int k = 0; k != 4; ++k)
    {
        print(alphabet[(i >> (2*k)) % 4]);
    }
}

Here 256 = 2^2 × 4, so you can easily generalize this scheme.

score 0 · Answer 9 · answered Jan 10 '12 at 22:26

A simple, straightforward javascript solution (season with braces to taste):

var letters = ['a', 'b', 'c', 'd'], len=letters.length;

for (var i=len; i--;) 
  for (var j=len; j--;) 
    for (var k=len; k--;) 
      for (var l=len; l--;) 
        console.log (letters[i] + letters[j] + letters[k] + letters[l]);

score 0 · Answer 10 · answered Jan 10 '12 at 22:56

Using Recursion, Action Delegate and Lambdas!!! (just for fun)

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            List<char> letters = new List<char>() { 'a', 'b', 'c', 'd' };
            List<string> words = new List<string>();
            Action<IEnumerable<char>, string, List<string>> recursiveLetter = null;

            recursiveLetter = (availLetters, word, newWords) =>
            {
                if (word.Length < availLetters.Count())
                {
                    availLetters.ToList()
                                .ForEach(currentletter => 
                                           recursiveLetter(availLetters, 
                                                           word + currentletter, 
                                                           newWords));
                }
                else
                {
                    newWords.Add(word);
                }
            };

            recursiveLetter(letters, string.Empty, words); // ALL THE MAGIC GO!

            words.ForEach(word => Console.WriteLine(word));
            Console.ReadKey();
        }
    }
}

What if he wants to print all combinations of length 5 of 3 or 4 letters? — ChrisWue, Jan 11 '12 at 01:19

score 0 · Answer 11 · answered Jan 11 '12 at 00:30

An implementation in C

#include <stdio.h>
#define WORD_LEN 5
#define ALPHA_LEN 4

char alphabet[ALPHA_LEN] = {'a', 'b', 'c', 'd'};
int w[WORD_LEN] = {};

void print_word() {
    int i;
    char s[WORD_LEN + 1];
    for(i = 0; i < WORD_LEN; i++) {
        s[i] = alphabet[w[i]];
    }
    s[WORD_LEN] = '\0';
    puts(s);
}

int increment_word() {
    int i;
    for(i = 0; i < WORD_LEN; i++) {
        if(w[i] < ALPHA_LEN - 1) {
            w[i]++;
            return 1;
        } else {
            w[i] = 0;
        }
    }
    return 0;
}

int main() {
    int i;
    do {
        print_word();
    } while (increment_word());
}

score 0 · Answer 12 · answered Jan 11 '12 at 14:18

0

Another Linq based answer:

List<string> items = new List<string>() {"a", "b", "c", "d"};
items.ForEach(i1 => 
  items.ForEach(i2 =>
    items.ForEach(i3 =>
      items.ForEach(i4 =>
        Console.WriteLine(i1 + i2 + i3 + i4)
      )
    )
  )
);

answered Jan 11 '12 at 14:18

Scott Brickey

1,207
12
22

score 0 · Answer 13 · answered Jan 11 '12 at 17:30

Haskell may well have the shortest program here:

sequence (replicate 4 "abcd")

replicate 4 "abcd" creates a list that repeats "abcd" four times. sequence is a very general, polymorphic, moadic operation that has many uses, among which is generating cartesian products of lists of lists.

It may be possible to duplicate this solution in C# or other .NET languages. Eric Lippert's LINQ solution corresponds to this Haskell solution:

items = ["a", "b", "c", "d"]

query = do i1 <- items
           i2 <- items
           i3 <- items
           i4 <- items
           return (i1 ++ i2 ++ i3 ++ i4)

If you compare them, well, note that LINQ's from ... in was inspired by Haskell's <-, and LINQ's select is Haskell's return.

The relationship between the Haskell one-liner solution and the longer one can be brought out by writing our own definition of sequence:

sequence' [] = return []
sequence' (m:ms) = do x <- m
                      xs <- sequence' ms
                      return (x:xs)

In LINQ terms, the sequence function allows you to replace the repeated from ix in items statements with just a list of the lists from which to choose each item.

EDIT: a friend just beat me at one-lining this (well, one line except for the import):

import Control.Monad

replicateM 4 "abcd"

score 0 · Answer 14 · answered Jan 11 '12 at 22:49

0

In Python:

items = ["a", "b", "c", "d"]

print [a + b + c+ d for a in items for b in items for c in items for d in items]

answered Jan 11 '12 at 22:49

score 0 · Answer 15 · answered Jan 12 '12 at 02:14

0

There must be an erlang list comprehension

Something like

Value = "abcd".
[ [A] ++ [B] ++ [C] ++ [D] || A <- Value, B <- Value, C <- Value, D <- Value ].

answered Jan 12 '12 at 02:14

thierry.henrio

66
3

How to get every possible pattern of an array of letters

15 Answers15

Linked