Getting word combinations from group of letters

Question

I searched over the internet a lot how to do this but I didn't came up with something I completely understood.

Im trying to generate all the possible combinations from an array of letters by specifying the amount of letters in each group, for example:

letters: A, B, C

length: 2

result: AB, AC, BC

(I know there are: BA, CA and CB too but I only need to get the groups the order isn't matter.)

example 2:

letters: A, B, C, D

length: 3

result: ABC, ACD, BCD, CDA, DAB

and etc…

I intend to implement that algorithm in C++ but examples in C#, Java or Javascript are welcome as well.

Appears to be quite closely related to [this question](http://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string). — Geoff, Apr 12 '12 at 15:35
Generating the partial groups might be more easy, if you produce them always in ascending order internally, like: 'abc', 'acd', 'bcd', 'acd', 'abd' ... and in order abc, abd, acd - ah, you got it twice! see! — user unknown, Apr 12 '12 at 15:37
Here's a Python implementation: http://docs.python.org/library/itertools.html#itertools.combinations — Mike Christensen, Apr 12 '12 at 15:48
Try to come up with a method, given all combinations of length N, to produce all combinations of length (N+1). — n. m. could be an AI, Apr 12 '12 at 15:51
@sch - Sorry, yes; you're right. Your question deals with combinations (as you originally stated), the other with permutations. Note that the accepted answer in my linked question should still give you a solution if you filter the items in the list as you add them; just create a ListAdd() function which sorts the chars in the incoming word, and adds it to the list if it's not already present. — Geoff, Apr 12 '12 at 18:38
Your problem could be easily solved with my [binomial coefficient class](http://tablizingthebinomialcoeff.wordpress.com/). Take a look at my [answer](http://stackoverflow.com/a/12604728/643828) to a somewhat related problem. — Bob Bryan, Sep 26 '12 at 17:26

score 1 · Answer 1 · answered Apr 12 '12 at 15:52

Seems like a good fit for recursion. Take each element, and prepend it to the remaining combinations until a given depth is met.

static List<String> func(List<String> a, Int32 depth)
{
    List<String> retVal = new List<String>();
    if (depth <= 0)
    {
        return retVal;
    }
    for (int i = 0; i < a.Count; i++)
    {
        String element = a[i];

        List<String> temp = new List<String>(a);
        temp.RemoveAt(i);
        List<String> resultset = func(temp, depth - 1);
        if (resultset.Count == 0)
        {
            retVal.Add(element);
        }
        else
        {

            foreach (String result in resultset)
            {
                retVal.Add(element + result);
            }
        }
    }
    return retVal;
}

score 1 · Accepted Answer · answered Apr 12 '12 at 15:53

If you order them in a reproducable way, you will find an algorithm to produce them more easily:

Let's make it not too easy, take 3 of 5:

e d c b a 
---------
    x x x abc
  x   x x abd
x     x x abe
  x x   x acd 
x   x   x ace
x x     x ade
  x x x   bcd
x   x x   bce
x x   x   bde 
x x x     cde

score 1 · Answer 3 · answered Dec 14 '15 at 16:40

This is known as permutation, there are lots of solutions for it. Here is a non-recursive one that I wrote which is super fast. (If you are on Windows, you may need to look-up _BitScanReverse instead of using __builtin_ctz).

#include <iostream>
#include <cstdlib>
using namespace std;

void perm(unsigned &v) { //v must be initialised with t = ( 2 << N ) - 1;
    unsigned t = v | (v - 1);
    v = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
}

int main (int argc, char *argv[]) {
    unsigned n = argc > 1 ? atoi(argv[1]) : 3; //bins:   0..31
    unsigned k = argc > 2 ? atoi(argv[2]) : 2; //things: 0 .. bins.
    unsigned m = (1 << n) - 1; //bitmask is size of n (bins).
    unsigned v = (1 << k) - 1; //start value - initial allocation.
    do {
        cout << bitset<31>(v & m) << endl;
        perm(v);
    } while (v < m);
    return 0;
}

In your question you suggest - letters: A, B, C length: 2 as an example. So, this code would generate (passing 3 2 as arguments) (which I have commented)

ABC
011 //BC
101 //AC
110 //AB

score 0 · Answer 4 · edited May 23 '17 at 12:07

This should work if you tweak it a little:

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

Explanation here.

Getting word combinations from group of letters

4 Answers4