Sources.RU Magazine Поиск по журналу
 

Ссылки

Перечисление всех возможных сочетаний элементов массива

Автор: bizar

Исходные данные: массив Array (0=>"1", 1=>"2", 2=>"3", 3=>"4", 4=>"5").

Цель: Вывести все возможные сочетания элементов (определить все возможные неповторяющиеся комбинации значений).

Пример массива:

1
2
3
12
13
23
123

Aloha предложил следующий алгоритм:

Всего наборов будет 2^n – 1 (не считая 0).
Перечислим все сочетания для n=5:

Десятичные от 1 до 2^n - 1 Двоичные Меняем порядок битов Заменяем значимый бит на его номер (слева направо) Результат
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111
10000
01000
11000
00100
10100
01100
11100
00010
10010
01010
11010
00110
10110
01110
11110
00001
10001
01001
11001
00101
10101
01101
11101
00011
10011
01011
11011
00111
10111
01111
11111
1....
.2...
12...
..3..
1.3..
.23..
123..
...4.
1..4.
.2.4.
12.4.
..34.
1.34.
.234.
1234.
....5
1...5
.2..5
12..5
..3.5
1.3.5
.23.5
123.5
...45
1..45
.2.45
12.45
..345
1.345
.2345
12345
1
2
12
3
13
23
123
4
14
24
124
34
134
234
1234
5
15
25
125
35
135
235
1235
45
145
245
1245
345
1345
2345
12345



Поясняю. Первым делом мы подсчитываем количество значений в массиве, затем подсчитываем количество всевозможных комбинаций по формуле 2^n – 1 (не считая 0). Далее для каждой десятичной цифры (не считая 0) мы выведем её в двоичном коде (к примеру, у 6-ти это будет 110). Следующим этапом будет дописывание 0 слева от получившегося результата на длину (количество значений в массиве, допустим у нас 5 значений, для 6 это будет 00110), далее меняем порядок битов (переворачиваем получившийся результат) – 01100. Вот и всё, теперь нужно заменить значение бита его номером (для 01100 это будет “ . 2 3 . . ”). Теперь рассмотрим, как это будет всё смотреться на языке php

// Создаём функцию struktura_array (массив со значениями)
function struktura_array($mas) {
//Подсчитываем количество значений в массиве $mas
$col_el = count($mas);
//Подсчитываем количество всевозможных вариантов по формуле 2^n – 1, n = $col_el
$col_zn = pow(2,$col_el)-1;

//Делаем цикл до $i = $col_zn
for ($i=1; $i <= $col_zn; $i++) {
//выполняем преобразование числа $i в двоичную систему
 $dlina_i_bin = decbin($i);
//Дописываем нули в левую часть на длину $col_el
 $zap_str = str_pad($dlina_i_bin, $col_el, "0", STR_PAD_LEFT);
//Переворачиваем $zap_str
 $zap_dop = strrev($zap_str);
 $dooh = array();
//Преобразуем $zap_dop в массив вида Array (0=>"0", 1=>"1", 2=>"1", 3=>"0", 4=>"0")
 for($j=0; $j < $col_el; $j++) {
 $dooh[] = $zap_dop[$j];
 }
//Обнуляем $d и $a чтоб при следующем проходе цикла они были пустыми
 $d = 0; $a = "";
//Теперь самое интересное
//Итерируем по массиву $dooh и выдергиваем значения (либо 1 либо 0)
 foreach ($dooh as $k=>$v) {
//Если выдернули 1 то в массив $a записываем значение с соответствующим ключом
   if ($v == 1) {$a[] .= $mas[$d];}
//Увеличиваем ключ на единицу для перехода по массиву
   $d++;
 }
 $return[] = $a;
}

return $return;
}

Вот и всё. Идея родилась на нашем форуме, когда мне понадобился этот алгоритм. Его придумал замечательный товарищ Aloha, а я реализовал его на php. Мне предлагали очень много вариантов алгоритма. Посмотреть все варианты и задать все вопросы вы можете тут: Перейти

С уважением, bizar!



Если у Вас возникли проблемы, вопросы или пожелания к статье – милости просим в тему поддержки этой статьи.



 Desingn by Шишкин Алексей (Лёха).
 ©2004-2008 by sources.ru.