Перестановки массива массивов строк

Question

Я просто не могу понять, как решить эту проблему, и после тщательного поиска в Google без результатов я обращаюсь к вам с надеждой на решение.

Учитывая образец массива ниже:

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

(Примечание. Это всего лишь пример; в реальной ситуации может быть меньше / больше групп и / или элементов на группу)

Как бы я закончил со следующим результатом?

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

Это поиск по продукту, и API допускает только ОДНО значение «уточнения» из каждой группы «Тип», «Размер» и «Цвет» для каждого запроса, но мое назначение требует запрашивать и объединять результаты нескольких запросов API.

Я думаю , что для этого мне нужна какая-то рекурсивная функция, но я не смог даже создать какой-либо код, близкий к моему ожидаемому результату.

Все, что я смог найти в Google, - это перестановки букв или даже строк, но там, где людям нужно, например. «Красный, синий, зеленый», «синий, красный, зеленый», «зеленый, красный, синий» и т. Д., Что, разумеется, не то, что я ищу.

Я надеюсь, что кто-то здесь понимает, что я хочу сделать, и знает, как это сделать.

РЕДАКТИРОВАТЬ: Решение, опубликованное @ikegami, преобразованное в 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";
}

Answer 1

Если бы у нас было три группы по десять предметов, мы могли бы использовать счетчик, который идет от 0 до 999, и разбить число на цифры.

Например,

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

ЭтоАлгоритм преобразует число в основание 10. Если бы мы хотели преобразовать в восьмеричное число, мы бы использовали 8 вместо 10. 10 (или 8) использовались повсеместно, потому что каждая позиция имеет одинаковое количество символов, но этот алгоритм также работает, есликоличество символов варьируется от позиции к позиции.

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

Это дает нам:

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

Ниже приведена реализация Perl:

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

Я знаюэто не PHP - я не знаю PHP - но вы просто спрашиваете, как решить проблему, а не обязательно код для этого, верно?Я надеюсь, что вы сможете понять приведенный выше код Perl в достаточной степени, чтобы решить вашу проблему и повторно реализовать его на PHP.

(Если бы я на самом деле писал решение на Perl, я бы использовал Algorith ::Петли х NestedLoops.)

Answer 2

Только для тех, кто хочет перевод PHP:

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'))));

Answer 3

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

Answer 4

Ну, я не достаточно умен, чтобы понять решение ikegami, но я смог преобразовать его в Javascript для своих целей. Я не знаю, как это работает, но это великолепно!

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))

Да, я оставил некоторые знаки $ для переменных из версии PHP.

Answer 5

Предположим, у вас есть только один уровень вложенности, то, что вы хотите:

$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])

то есть вы видите проблему как необходимость соединить два списка / массива. Первый - первый подмассив вашего массива, а второй - (уже рекурсивно сделанный) остаток.

Итак, вам нужна такая функция:

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

, где $group1 - первый подмассив вашего массива, а $group_rest - это то, что осталось. Итак:

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

, но $rest также является массивом, поэтому вам также нужно выполнить цикл по нему:

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

добавьте конечное условие (null $group_rest), и вы установите:

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