PHP Найти все (несколько) уникальные комбинации массива

Если вы не возражаете использовать пару глобальных переменных, вы можете сделать это в PHP (в переводе с версии на JavaScript):

 <?PHP $result = array(); $combination = array(); function combinations(array $myArray, $choose) { global $result, $combination; $n = count($myArray); function inner ($start, $choose_, $arr, $n) { global $result, $combination; if ($choose_ == 0) array_push($result,$combination); else for ($i = $start; $i <= $n - $choose_; ++$i) { array_push($combination, $arr[$i]); inner($i + 1, $choose_ - 1, $arr, $n); array_pop($combination); } } inner(0, $choose, $myArray, $n); return $result; } print_r(combinations(array(20,20,22,24), 3)); ?> 

ВЫВОД:

 Array ( [0] => Array ( [0] => 20 [1] => 20 [2] => 22 ) [1] => Array ( [0] => 20 [1] => 20 [2] => 24 ) [2] => Array ( [0] => 20 [1] => 22 [2] => 24 ) [3] => Array ( [0] => 20 [1] => 22 [2] => 24 ) ) 

Пакет груши Math_Combinatorics делает эту проблему довольно простой. Он требует относительно небольшого кода, он прост и прост, и его довольно легко прочитать.

 $ cat code/php/test.php <?php $input = array(20, 20, 22, 24); require_once 'Math/Combinatorics.php'; $c = new Math_Combinatorics; $combinations = $c->combinations($input, 3); for ($i = 0; $i < count($combinations); $i++) { $vals = array_values($combinations[$i]); $s = implode($vals, ", "); print $s . "\n"; } ?> $ php code/php/test.php 20, 20, 22 20, 20, 24 20, 22, 24 20, 22, 24 

Если бы мне пришлось упаковать это как функцию, я бы сделал что-то вроде этого.

 function combinations($arr, $num_at_a_time) { include_once 'Math/Combinatorics.php'; if (count($arr) < $num_at_a_time) { $arr_count = count($arr); trigger_error( "Cannot take $arr_count elements $num_at_a_time " ."at a time.", E_USER_ERROR ); } $c = new Math_Combinatorics; $combinations = $c->combinations($arr, $num_at_a_time); $return = array(); for ($i = 0; $i < count($combinations); $i++) { $values = array_values($combinations[$i]); $return[$i] = $values; } return $return; } 

Это вернет массив массивов. Получить текст. , ,

 <?php include_once('combinations.php'); $input = array(20, 20, 22, 24); $output = combinations($input, 3); foreach ($output as $row) { print implode($row, ", ").PHP_EOL; } ?> 20, 20, 22 20, 20, 24 20, 22, 24 20, 22, 24 

Если вы ищете уникальные комбинации, которые из вашего тестового примера 4 выбирают 3: 0 1 2 0 1 3 0 2 3 1 2 3

то ваша проблема подпадает под биномиальный коэффициент.

Я написал класс в C # для обработки общих функций для работы с биномиальным коэффициентом, который классифицируется по формуле n! / (n! * (nk)!), где n – количество элементов, а k – число, в которое они группируются. Он выполняет следующие задачи:

1. Выводит все K-индексы в хорошем формате для любого N, выбирающего K в файл. K-индексы могут быть заменены более описательными строками или буквами.

2. Преобразует K-индексы в соответствующий лексикографический индекс или ранги записи в таблице отсортированных биномиальных коэффициентов. Этот метод намного быстрее, чем более старые опубликованные методы, основанные на итерации. Он делает это, используя математическое свойство, присущее Треугольнику Паскаля, и является очень эффективным по сравнению с итерацией по множеству.

3. Преобразует индекс в отсортированную таблицу биномиальных коэффициентов в соответствующие K-индексы. Я считаю, что это также быстрее, чем более старые итерационные решения.

4. Использует метод Mark Dominus для вычисления биномиального коэффициента, который гораздо реже переполняется и работает с большими числами.

5. Класс написан на .NET C # и предоставляет способ управления объектами, связанными с проблемой (если есть), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое, когда true, создаст общий список для хранения объектов, которые будут управляться. Если это значение ложно, то оно не создаст таблицу. Таблицу не нужно создавать, чтобы использовать 4 вышеуказанных метода. Для доступа к таблице предоставляются методы доступа.

6. Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был широко протестирован с 2 случаями, и нет известных ошибок.

Чтобы прочитать об этом классе и загрузить код, см. Tablizing The Binomial Coeffieicent .

Следующий протестированный код будет проходить через каждую уникальную комбинацию:

 public void Test10Choose5() { String S; int Loop; int N = 10; // Total number of elements in the set. int K = 5; // Total number of elements in each group. // Create the bin coeff object required to get all // the combos for this N choose K combination. BinCoeff<int> BC = new BinCoeff<int>(N, K, false); int NumCombos = BinCoeff<int>.GetBinCoeff(N, K); // The Kindexes array specifies the indexes for a lexigraphic element. int[] KIndexes = new int[K]; StringBuilder SB = new StringBuilder(); // Loop thru all the combinations for this N choose K case. for (int Combo = 0; Combo < NumCombos; Combo++) { // Get the k-indexes for this combination. BC.GetKIndexes(Combo, KIndexes); // Verify that the Kindexes returned can be used to retrive the // rank or lexigraphic order of the KIndexes in the table. int Val = BC.GetIndex(true, KIndexes); if (Val != Combo) { S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString(); Console.WriteLine(S); } SB.Remove(0, SB.Length); for (Loop = 0; Loop < K; Loop++) { SB.Append(KIndexes[Loop].ToString()); if (Loop < K - 1) SB.Append(" "); } S = "KIndexes = " + SB.ToString(); Console.WriteLine(S); } } 

Вы должны легко переносить этот класс на PHP. Вам, вероятно, не придется переносить общую часть класса для достижения ваших целей. В зависимости от количества комбинаций, с которыми вы работаете, вам может потребоваться использовать более крупный размер слова, чем 4 байта int. Вы должны определить массив или список с вашими интересными объектами, а затем просто проиндексировать этот массив с каждым элементом в k-индексах.

Идея проста. Предположим, вы знаете, как переставить, тогда, если вы сохраните эти перестановки в наборе, это станет комбинацией. По определению по умолчанию учитываются повторяющиеся значения. Эквивалентом Php для Set или HashSet является SplObjectStorage и ArrayList – массив. Это не должно быть трудно переписать. У меня есть реализация в Java:

 public static HashSet<ArrayList<Integer>> permuteWithoutDuplicate(ArrayList<Integer> input){ if(input.size()==1){ HashSet<ArrayList<Integer>> b=new HashSet<ArrayList<Integer>>(); b.add(input); return b; } HashSet<ArrayList<Integer>>ret= new HashSet<ArrayList<Integer>>(); int len=input.size(); for(int i=0;i<len;i++){ Integer a = input.remove(i); HashSet<ArrayList<Integer>>temp=permuteWithoutDuplicate(new ArrayList<Integer>(input)); for(ArrayList<Integer> t:temp) t.add(a); ret.addAll(temp); input.add(i, a); } return ret; } 

Почему бы просто не использовать двоичный код? По крайней мере, тогда его просто и очень легко понять, что каждая строка кода действительно нравится? Вот функция, которую я написал для себя в проекте, который я считаю довольно аккуратным!

 function search_get_combos($array){ $bits = count($array); //bits of binary number equal to number of words in query; //Convert decimal number to binary with set number of bits, and split into array $dec = 1; $binary = str_split(str_pad(decbin($dec), $bits, '0', STR_PAD_LEFT)); while($dec < pow(2, $bits)) { //Each 'word' is linked to a bit of the binary number. //Whenever the bit is '1' its added to the current term. $curterm = ""; $i = 0; while($i < ($bits)){ if($binary[$i] == 1) { $curterm[] = $array[$i]." "; } $i++; } $terms[] = $curterm; //Count up by 1 $dec++; $binary = str_split(str_pad(decbin($dec), $bits, '0', STR_PAD_LEFT)); } return $terms; } 

Для вашего примера это означает:

 Array ( [0] => Array ( [0] => 24 ) [1] => Array ( [0] => 22 ) [2] => Array ( [0] => 22 [1] => 24 ) [3] => Array ( [0] => 20 ) [4] => Array ( [0] => 20 [1] => 24 ) [5] => Array ( [0] => 20 [1] => 22 ) [6] => Array ( [0] => 20 [1] => 22 [2] => 24 ) [7] => Array ( [0] => 20 ) [8] => Array ( [0] => 20 [1] => 24 ) [9] => Array ( [0] => 20 [1] => 22 ) [10] => Array ( [0] => 20 [1] => 22 [2] => 24 ) [11] => Array ( [0] => 20 [1] => 20 ) [12] => Array ( [0] => 20 [1] => 20 [2] => 24 ) [13] => Array ( [0] => 20 [1] => 20 [2] => 22 ) [14] => Array ( [0] => 20 [1] => 20 [2] => 22 [3] => 24 ) ) 

Имел ту же проблему и нашел другое и побитовое, более быстрое решение:

 function bitprint($u) { $s = array(); for ($n=0; $u; $n++, $u >>= 1){ if ($u&1){ $s [] = $n; } } return $s; } function bitcount($u) { for ($n=0; $u; $n++, $u = $u&($u-1)); return $n; } function comb($c,$n) { $s = array(); for ($u=0; $u<1<<$n; $u++){ if (bitcount($u) == $c){ $s [] = bitprint($u); } } return $s; } 

Он генерирует все комбинации m размера целых чисел от 0 до n-1, поэтому, например, m = 2, n = 3 и вызов гребня (2, 3) будет производить:

 0 1 0 2 1 2 

Он дает вам индексные позиции, поэтому легко указывать на элементы массива по индексу.

Изменить: сбой входного гребня (30, 5). Не знаю, почему, кто-нибудь идеи?

Очистил вздор Ади Брэдфилда, используя strev и for / foreach, и получил только уникальные результаты.

 function search_get_combos($array = array()) { sort($array); $terms = array(); for ($dec = 1; $dec < pow(2, count($array)); $dec++) { $curterm = array(); foreach (str_split(strrev(decbin($dec))) as $i => $bit) { if ($bit) { $curterm[] = $array[$i]; } } if (!in_array($curterm, $terms)) { $terms[] = $curterm; } } return $terms; }