Алгоритм - генерация всех комбинаций из предметов, которые должны быть выбраны в последовательности - PullRequest
Новая
       24

Алгоритм - генерация всех комбинаций из предметов, которые должны быть выбраны в последовательности

5 голосов
/ 18 ноября 2011

Я хочу выяснить, существует ли уже определенный алгоритм. Я хочу использовать его в приложении, но я также видел, как это возникало в нескольких Project Euler проблемах тоже.

Я рассчитываю рассчитать определенный тип набора перестановок / выходов, где следующий выбранный элемент должен быть одним из конечного набора параметров только в следующем наборе.

Например, скажем, у меня есть 3 массива 

$a1 = array("a", "b", "c");
$a2 = array("d", "e", "f");
$a3 = array("g", "h", "i");

Я хочу сгенерировать все возможности последовательности, содержащей не более 1 элемента из каждого массива , , выбранного в порядке . То есть в качестве результата я хотел бы видеть: 

adg aeg afg
adh aeh afh
adi aei afi

bdg beg bfg 
bdh beh bfh
bdi bei bfi

cdg ceg cfg
cdh ceh cfh
cdi cei cfi

Глядя, чтобы реализовать алгоритм в PHP или Javascript. По сути, он будет проходить через переменное число массивов, содержащих переменное количество элементов, и выводить все возможные последовательности, которые могут встречаться в последовательном порядке.

Это существует?

Если так, как это называется? Технически это не перестановка или комбинация из того, что я знаю об обоих.

РЕДАКТИРОВАТЬ: Даниэль Фишер сообщил мне, что это декартово произведение, вот реализация взято с сайта PHP : 

function array_cartesian_product($arrays)
{
    $result = array();
    $arrays = array_values($arrays);
    $sizeIn = sizeof($arrays);
    $size = $sizeIn > 0 ? 1 : 0;
    foreach ($arrays as $array)
        $size = $size * sizeof($array);
    for ($i = 0; $i < $size; $i ++)
    {
        $result[$i] = array();
        for ($j = 0; $j < $sizeIn; $j ++)
            array_push($result[$i], current($arrays[$j]));
        for ($j = ($sizeIn -1); $j >= 0; $j --)
        {
            if (next($arrays[$j]))
                break;
            elseif (isset ($arrays[$j]))
                reset($arrays[$j]);
        }
    }
    return $result;
}

Ответы [ 4 ]

2 голосов
/ 18 ноября 2011

Это декартово произведение, если из каждого списка / массива выбран ровно один элемент, точнее, список элементов декартового произведения. Для списков, это в стандартной библиотеке Haskell: 

Prelude> sequence ["abc","def","ghi"]
["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh"
,"bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]

Я думаю, для PHP или Javascript, вы должны кодировать его самостоятельно.

0 голосов
/ 18 ноября 2011

В Mathematica это изначально реализовано как Tuples. 

Tuples[{{a, b, c}, {d, e, f}, {g, h, i}}]

{{a, d, g}, {a, d, h}, {a, d, i}, {a, e, g}, {a, e, h}, {a, e, i},
 {a, f, g}, {a, f, h}, {a, f, i}, {b, d, g}, {b, d, h}, {b, d, i},
 {b, e, g}, {b, e, h}, {b, e, i}, {b, f, g}, {b, f, h}, {b, f, i},
 {c, d, g}, {c, d, h}, {c, d, i}, {c, e, g}, {c, e, h}, {c, e, i},
 {c, f, g}, {c, f, h}, {c, f, i}}

Это также можно сделать с помощью Outer (обобщенное внешнее произведение): 

Outer[List, {a, b, c}, {d, e, f}, {g, h, i}]

Или с итерацией (Table): 

Table[{x, y, z},
 {x, {a, b, c}},
 {y, {d, e, f}},
 {z, {g, h, i}}
]

Или с рекурсией: 

sets[{}, c__] := {{c}}
sets[{x_, r___}, c___] := Join @@ (sets[{r}, c, #] & /@ x)

sets[{{a, b, c}, {d, e, f}, {g, h, i}}]
0 голосов
/ 18 ноября 2011

Я думаю, что вы правы, что это не перестановка и не комбинация, потому что длина строки фиксирована в вашем случае. Извините за использование java [7], но я знаю его лучше всего. 

public abstract class AFixedPermutation {
   private char[][] fields;
   private StringBuilder sb = new StringBuilder();
   private int[] callvec;
   private int maxDepth;

   public FixedPermutation(char[][] fields) { 
     this.fields = fields; 

     callvec = new int[fields.length];
     for (int i = 0; i < fields.length; i++) callvec[i] = 0;
     maxDepth = callvec.length - 1;
     recurse(0);
   }

   protected abstract emit(String s);

   private void recurse(int depth) {
     for (int i = 0; i < fields[depth].length; i++) { 
        callvec[depth] = i;
        if (depth == maxDepth) { apply(); }
        else {recurse(depth + 1); }
     }
   }

   private void apply() {
      sb.setLength(0);
      for (int i = 0; i < callvec.length; i++) {
        sb.append(fields[i][callvec[i]]);
      }
      emit(sb.toString());
   }
}
0 голосов
/ 18 ноября 2011

Вы можете пройти через элементы в цикле.Например, вы можете сделать следующее для вашего случая: 

var ret = [];
for (var i=0; i<a1.length; i++) {
  for (var j=0; j<a2.length; j++) {
    for (var k=0; k<a3.length; k++) {
      ret.push( [a1[i], a2[j], a3[k]] );
    }
  }
}
// do stuff with ret

Обратите внимание, что это довольно медленно, особенно если у вас много массивов очень длинных массивов.Для Project Euler обычно есть и другие идеи, которые вы можете использовать вместо перечисления всего.

...