Permutations of an array of arrays of strings

I simply cannot wrap my head around how to 开发者_如何学Pythonsolve this problem and after a thorough search on Google with no results, I turn to you with hopes of a solution.

Given the sample array below:

array(
    'Type' => array(
        'Toppe',
        'Bukser_og_Jeans'
    ),
    'Size' => array(
        'Extra_small',
        'Small'
    ),
    'Colour' => array(
        'Rod'
    )
)

(Note: This is merely a sample; the actual real life situation might have less/more groups and/or elements per group)

How would I go about ending up with the following result?

Toppe,Extra_small,Rod
Toppe,Small,Rod
Bukser_og_Jeans,Extra_small,Rod
Bukser_og_Jeans,Small,Rod

This is a product search and the API only allows ONE 'refinement' value from each of the Type, Size and Colour groups per query but my assignment requires to query and aggregate the results of multiple API queries.

I'm thinking that I need some kind of recursive function to do it, but I have been unable to even produce any code that comes close to my expected result.

All I've been able to find on Google is about permuations of letters or even strings, but where people need e.g. "Red,Blue,Green", "Blue,Red,Green", "Green,Red,Blue", etc., which is, clearly, not what I'm looking for.

I hope someone here understands what I want to do and has an idea of how to do it.

EDIT: The solution as posted by @ikegami, converted to PHP:

$iter = 0;
while (1) {
    $num = $iter++;
    $pick = array();

    foreach ($refinements as $refineGroup => $groupValues) {
        $r = $num % count($groupValues);
        $num = ($num - $r) / count($groupValues);
        $pick[] = $groupValues[$r];
    }

    if ($num > 0) {
        break;
    }

    print join(', ', $pick)."\n";
}

If we had three groups of ten items, we could use a counter that goes from 0 to 999, and split the number into digits.

For example,

456 
   % 10 = 6  --------------------------  Item 6 (7th item) in the first group
   / 10 = 45
             % 10 = 5  ----------------  Item 5 (6th item) in the second group
             / 10 = 4
                       % 10 = 4  ------  Item 4 (5th item) in the third group
                       / 10 = 0

This algorithm converts a number into base 10. If we wanted to convert to octal, we would have used 8 instead of 10. 10 (or 8) is used throughout because each position has the same number of symbols, but this algorithm also works if the number of symbols varies from position to position.

2
   % 2 = 0  ------------------------  Item 0 (1st item) in the first group: Toppe
   / 2 = 1
     ^      % 2 = 1  ---------------  Item 1 (2nd item) in the second group: Small
     |      / 2 = 0
     |        ^      % 1 = 0  ------  Item 0 (1st item) in the third group: Rod
     |        |      / 1 = 0
     |        |        ^
     |        |        |
     |        |        +------------  Number of items in third group
     |        +---------------------  Number of items in second group
     +------------------------------  Number of items in first group

This gives us:

0 = ( 0 * 1 + 0 ) * 2 + 0 = Toppe, Extra_small, Rod
1 = ( 0 * 1 + 0 ) * 2 + 1 = Bukser_og_Jeans, Extra_small, Rod
2 = ( 0 * 1 + 1 ) * 2 + 0 = Toppe, Small, Rod
3 = ( 0 * 1 + 1 ) * 2 + 1 = Bukser_og_Jeans, Small, Rod

The following is a Perl implementation:

my %refinements = (
   Type => [
      'Toppe',
      'Bukser_og_Jeans',
   ],
   Size => [
      'Extra_small',
      'Small',
   ],
   Colour => [
      'Rod',
   ],
);

my @groups = values(%refinements);
my $iter = 0;
while (1) {
   my $num = $iter++;

   my @pick;
   for my $group (@groups) {
      my $r = $num % @$group;
      $num = ( $num - $r ) / @$group;
      push @pick, $group->[$r];
   }

   last if $num > 0;

   say join(', ', @pick);
}

I know it's not PHP—I don't know PHP—but you're just asking how to solve the problem, not necessarily the code to do it, right? It's my hope that you can understand the above Perl code enough to solve your problem and re-implement it in PHP.

(If I was actually writing a Perl solution, I'd use Algorith::Loops's NestedLoops.)

Just for those wanting a PHP translation:

function factor_permutations($lists) {

    $permutations = array();
    $iter = 0;

    while (true) {

        $num = $iter++;
        $pick = array();

        foreach ($lists as $l) {
            $r = $num % count($l);
            $num = ($num - $r) / count($l);
            $pick[] = $l[$r];
        }

        if ($num > 0) break;
        $permutations[] = $pick;
    }

    return $permutations;
}

print_r(factor_permutations(array(array('a', 'b'), array('1', '2', '3'), array('foo', 'bar'))));

for ($i = 0; i < sizeof($Type); $i++) {
  for ($j = 0; j < sizeof($Size); $j++) {
     for ($k = 0; k < sizeof($Colour); $k++) {
       echo $Type[i] . $Size[j] . $Colour[k];
     }
  }
}

Well I am not clever enough to comprehend ikegami's solution but I was able to convert it to Javascript for my purposes. I don't know how it works but it is brilliant!

lists = [["a","b"],["x","y"],["1","2","3"]] 

function factorPermutations(lists) {  

permutations = []
$iter = 0;

while (1) {

    $num = $iter++;
    $pick = []; 

    for (l in lists) {
        $r = $num % (lists[l].length );
        $num = ($num - $r) / lists[l].length;
        $pick.push( lists[l][$r])
    } 
    if ($num > 0) break;

    permutations.push( $pick);
}
    return permutations
} 

console.log(factorPermutations(lists))

Yeah, I left some of the $ signs on variables from the PHP version.

Supposing you have only one nesting level, what you want is:

$my_ar[group1][0].(rest_of_the_group_perms[0])
$my_ar[group1][0].(rest_of_the_group_perms[1])
...
$my_ar[group1][N].(rest_of_the_group_perms[K])

that is, you can see the problem as having to join two lists/arrays. The first being the first subarray of your array and the second being the (recursively already made) rest.

So you need a function like this:

perms($my_arr) {
   foreach($elem in $group1) {
      $return_list[] = $elem.$rest;
   }
}

where $group1 is the first subarray of your array and $group_rest is what is left. So:

perms($my_arr) {
   $group1 = head($my_arr);
   $group_rest = tail($my_arr);

   $rest = perms($group_rest);
   $return_list = array();
   foreach($elem in $group1) {
      $return_list[] = "$elem, $rest";
   }
   return $return_list;
}

but $rest is also an array so you have to loop over that too:

perms($my_arr) {
   $group1 = head($my_arr);
   $group_rest = tail($my_arr);

   $rest = perms($group_rest);
   $return_list = array();
   foreach($elem in $group1) {
      foreach($relem in $rest) {
          $return_list[] = $elem.$relem;
      }
   }
   return $return_list;
}

add the ending condition (null $group_rest) and you are set:

perms($my_arr) {
   $group1 = head($my_arr);
   $group_rest = tail($my_arr);

  if (length($group_rest) == 0) 
       $rest = array();
  else
       $rest = perms($group_rest);
   $return_list = array();
   foreach($elem in $group1) {
      foreach($relem in $rest) {
          $return_list[] = $elem.$relem;
      }
   }
   return $return_list;
}