Get possible combinations of arrays

Question

SO

Problem

From SQL I get 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 general, combinations of 4 elements e tc). To be more specific: I mean combinations in the mathematical sense (without duplicates), i.e. Those considered equal

-so for the array above, which will be 10 for both pairs and triplets.

My approach

I started by comparing possible values ​​for with a possible selection of selected items. My current solution is to indicate if the item is selected as "1" and "0" otherwise. For the example above, this would 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 have to do is somehow create the desired set of bits. Here is 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 decided to save my bits as a regular string. My algorithm for creating the following association:

• Try to find "01". If not found, then this is 11..100..0 case (so this is the maximum, can no longer be found). If found, go to the second step
• Go to the right position "01" in the line. Switch it to position "10", and then move all zeros that are sharper than "position 01" to the left. For example, 01110 : the most correct position "01" is 0, so first we switch this "01" to "10". The line is now 10110 . Now go to the right side (this is without part 10 , so it starts with 0 + 2 = 2nd character) and moves all zeros to the left, i.e. 110 will be 011 . As a result, we have 10 + 011 = 10111 as the next association for 01110 .

I found a similar problem here - but there the OP wants combinations with duplicates, while I want them without duplication.

Question

My question is about two points:

• For my solution, could there be another way to make the next bit more efficient?
• Maybe there are simpler solutions for this? This seems to be a standard problem.

Answer 1

I'm sorry that I do not offer a PHP solution because I have not programmed PHP for a long time, but let me show you a quick Scala solution. Perhaps this 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, the real Scala code should be much more general in terms of the accepted element type and collection types, but I just wanted to show the main idea, and not the most beautiful Scala code.

Answer 2

Here is a recursive solution:

 function subcombi($arr, $arr_size, $count) { $combi_arr = array(); if ($count > 1) { for ($i = $count - 1; $i < $arr_size; $i++) { $highest_index_elem_arr = array($i => $arr[$i]); foreach (subcombi($arr, $i, $count - 1) as $subcombi_arr) { $combi_arr[] = $subcombi_arr + $highest_index_elem_arr; } } } else { for ($i = $count - 1; $i < $arr_size; $i++) { $combi_arr[] = array($i => $arr[$i]); } } return $combi_arr; } function combinations($arr, $count) { if ( !(0 <= $count && $count <= count($arr))) { return false; } return $count ? subcombi($arr, count($arr), $count) : array(); } $input_arr = array('foo', 'bar', 'baz', 'bee', 'feo'); $combi_arr = combinations($input_arr, 3); var_export($combi_arr); echo ";\n"; OUTPUT: array ( 0 => array ( 0 => 'foo', 1 => 'bar', 2 => 'baz', ), 1 => array ( 0 => 'foo', 1 => 'bar', 3 => 'bee', ), 2 => array ( 0 => 'foo', 2 => 'baz', 3 => 'bee', ), 3 => array ( 1 => 'bar', 2 => 'baz', 3 => 'bee', ), 4 => array ( 0 => 'foo', 1 => 'bar', 4 => 'feo', ), 5 => array ( 0 => 'foo', 2 => 'baz', 4 => 'feo', ), 6 => array ( 1 => 'bar', 2 => 'baz', 4 => 'feo', ), 7 => array ( 0 => 'foo', 3 => 'bee', 4 => 'feo', ), 8 => array ( 1 => 'bar', 3 => 'bee', 4 => 'feo', ), 9 => array ( 2 => 'baz', 3 => 'bee', 4 => 'feo', ), ); 

The recursion is based on the fact that in order to get all combinations of k ( $count ) elements from n ( $arr_size ), for all possible options for choosing the highest index based on zero i , find all the "subcombinations" of elements k-1 from the remaining elements i with an index below i .

An array is not array_slice d when it passed recursive calls to use the PHP lazy copy mechanism. Thus, there is no real copying since the array does not change.

Saving array indices is nice for debugging purposes, but it's optional. Surprisingly, simply removing $i => elements and replacing array + with array_merge causes a significant slowdown. To achieve a slightly better speed than the original version, you should do this:

 function subcombi($arr, $arr_size, $count) { $combi_arr = array(); if ($count > 1) { for ($i = $count - 1; $i < $arr_size; $i++) { $highest_index_elem = $arr[$i]; foreach (subcombi($arr, $i, $count - 1) as $subcombi_arr) { $subcombi_arr[] = $highest_index_elem; $combi_arr[] = $subcombi_arr; } } } else { for ($i = $count - 1; $i < $arr_size; $i++) { $combi_arr[] = array($arr[$i]); } } return $combi_arr; } 

---

As for the first part of your question, you should avoid calculating the same amount more than once, and you should minimize function calls. For example, for example:

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

It’s hard to make deeper changes to your code without turning it inside out. This is not so bad though, since in my tests its speed is approximately equal to half of my recursive solution (i.e. Times are close to doubling)

Answer 3

I just tried to solve this problem with minimal time complexity and without using recursion using go language.

I have seen several solutions, but using a recursive function. Prevention of recursion to solve the problem of exceeding the size of the stack.

 package main import "fmt" func main() { // Arguments arr := []string{"foo", "bar", "baz", "bee", "feo", "boo", "bak"} combinations := make([][]string, 0) k := 4 n := len(arr) // Execution starts from here if k > n { panic("invalid requirement") } pos := make([]int, k) // this variable is used to plot the unique combination of elements // initialize an array with first ever plotting possitions i := 0 c := k for c > 0 { c-- pos[i] = c i++ } combinations = append(combinations, getCombination(arr, pos, k)) // Let begin the work x := 0 ctr := 1 // counter is use to calculate total iterations for pos[x] < n-(x+1) { ctr++ pos[x]++ combinations = append(combinations, getCombination(arr, pos, k)) if pos[x] == n-(x+1) && x+1 < k { x++ i := x s := pos[x] + 1 for i > 0 { i-- s++ pos[i] = s } // continue to next index continue } x = 0 } fmt.Println("total # iterations: --> ", ctr) fmt.Println(combinations, "\ntotal # combinations: ", len(combinations)) } func getCombination(arr []string, pos []int, k int) []string { combination := make([]string, k) for i, j := k-1, 0; i >= 0; i, j = i-1, j+1 { combination[j] = arr[pos[i]] } return combination } 

A working example is here https://play.golang.org/p/D6I5aq8685-