Get possible array combinations

Question

SO,

The problem

From SQL I'm getting an array with strings (flat array) - let it be

$rgData = ['foo', 'bar', 'baz', 'bee', 'feo'];

Now, I want to get possible combinations of pairs and triplets of this array (and, in common case, combinations of 4 elements e t.c.). To be more specific: I mean combinations in math sense (without duplicates), i.e. those, which count is equal to

-so for array above that will be 10 for both pairs and triplets.

My approach

I've started from mapping possible values for to possible array selected items. My current solution is to point if an element is selected as "1", and "0" otherwise. For sample above that will be:

foo bar baz bee feo
 0   0   1   1   1   -> [baz, bee, feo]
 0   1   0   1   1   -> [bar, bee, feo]
 0   1   1   0   1   -> [bar, baz, feo]
 0   1   1   1   0   -> [bar, baz, bee]
 1   0   0   1   1   -> [foo, bee, feo]
 1   0   1   0   1   -> [foo, baz, feo]
 1   0   1   1   0   -> [foo, baz, bee]
 1   1   0   0   1   -> [foo, baz, feo]
 1   1   0   1   0   -> [foo, bar, bee]
 1   1   1   0   0   -> [foo, bar, baz]

And all I need to do is somehow produce desired bit set. Here's my code in PHP:

function nextAssoc($sAssoc)
{
   if(false !== ($iPos = strrpos($sAssoc, '01')))
   {
      $sAssoc[$iPos]   = '1';
      $sAssoc[$iPos+1] = '0';
      return substr($sAssoc, 0, $iPos+2).
             str_repeat('0', substr_count(substr($sAssoc, $iPos+2), '0')).
             str_repeat('1', substr_count(substr($sAssoc, $iPos+2), '1'));
   }
   return false;
}

function getAssoc(array $rgData, $iCount=2)
{
   if(count($rgData)<$iCount)
   {
      return null;
   }
   $sAssoc   = str_repeat('0', count($rgData)-$iCount).str_repeat('1', $iCount);
   $rgResult = [];
   do
   {
      $rgResult[]=array_intersect_key($rgData, array_filter(str_split($sAssoc)));
   }
   while($sAssoc=nextAssoc($sAssoc));
   return $rgResult;
}

-I've chosen to store my bits as a normal string. My algorithm for producing next association is:

1. Try to find "01". If not found, then it's 11..100..0 case (so it's maximum, no more could be found). If found, go to second step
2. Go to most right position of "01" in string. Switch it to "10" and then move all zeros that are righter than found "01" position - to left. For example, 01110: the most right position of "01" is 0, so first we switch this "01" to "10". String now sill be 10110. Now, go to right part (it's without 10 part, so it starts from 0+2=2-nd symbol), and move all zeros to left, i.e. 110 will be 011. As result, we have 10+011=10111 as next association for 01110.

I've found similar problem here - but there OP wants combinations with duplicates, while I want them without duplicated.

The question

My question is about two points:

• For my solution, may be there's another way to produce next bit set more efficient?
• May be there are more simple solutions for this? It seems to be standard problem.

Answer 1

I'm sorry for not providing a PHP solution, because I didn't program in PHP for quite a long time now, but let me show you a quick Scala solution. Maybe it will inspire you:

val array = Vector("foo", "bar", "baz", "bee", "feo")
for (i <- 0 until array.size; 
     j <- i + 1 until array.size; 
     k <- j + 1 until array.size)      
    yield (array(i), array(j), array(k))

Result:

Vector((foo,bar,baz), (foo,bar,bee), (foo,bar,feo), (foo,baz,bee), (foo,baz,feo), (foo,bee,feo), (bar,baz,bee), (bar,baz,feo), (bar,bee,feo), (baz,bee,feo))

Universal code for generating k-combinations:

def combinations(array: Vector[String], k: Int, start: Int = 0): Iterable[List[String]] = { 
  if (k == 1 || start == array.length) 
    for (i <- start until array.length) yield List(array(i))
  else 
    for (i <- start until array.length; c <- combinations(array, k - 1, i + 1)) yield array(i) :: c 
}

Results:

scala> combinations(Vector("a", "b", "c", "d", "e"), 1)
res8: Iterable[List[String]] = Vector(List(a), List(b), List(c), List(d), List(e))

scala> combinations(Vector("a", "b", "c", "d", "e"), 2)
res9: Iterable[List[String]] = Vector(List(a, b), List(a, c), List(a, d), List(a, e), List(b, c), List(b, d), List(b, e), List(c, d), List(c, e), List(d, e))

scala> combinations(Vector("a", "b", "c", "d", "e"), 3)
res10: Iterable[List[String]] = Vector(List(a, b, c), List(a, b, d), List(a, b, e), List(a, c, d), List(a, c, e), List(a, d, e), List(b, c, d), List(b, c, e), List(b, d, e), List(c, d, e))

scala> combinations(Vector("a", "b", "c", "d", "e"), 4)
res11: Iterable[List[String]] = Vector(List(a, b, c, d), List(a, b, c, e), List(a, b, d, e), List(a, c, d, e), List(b, c, d, e))

scala> combinations(Vector("a", "b", "c", "d", "e"), 5)
res12: Iterable[List[String]] = Vector(List(a, b, c, d, e))

Of course, real scala code should be much more generic with regard to accepted type of elements and type of collections, but I just wanted to show the basic idea, not the most beautiful Scala code possible.