Как найти алгоритм?

Question

[Selbi]

Уважаемые коллеги, не могу никак решить задачку, прошу помощи. Разрабатываю учебный проект, и там мне нужно сделать следующее:
Дано:
$array = [1, 2, 3, 4, 5];

Результат:
1 | 2 | 3
1 | 2 | 4
1 | 2 | 5
1 | 3 | 4
1 | 3 | 5
1 | 4 | 5
2 | 3 | 4
2 | 3 | 5
2 | 4 | 5
3 | 4 | 5

Есть вышеуказанный массив чисел (для примера, на самом деле там слова, но это думаю не важно). Из этого массива нужно получить всевозможные варианты строк, состоящих из 3 чисел. Только порядок очень важен, нарушать его нельзя, то есть как в массиве и 5 | 2 | 1 например не можем сделать. На словах то знаю как это делается, выше приведен пример из всевозможных вариантов, но как это описать в коде не знаю. Суть в том, что берем первые 2 элемента (1 и 2 получается) и 3 элемент подставляем из остальных элементов массива, так и получаем 1|2|n где n все элементы массива, которые не попали на первые 2 места, далее берем 1|3|n, 1|4|n и так до конца.

P.S. Никаких дублей не должно быть, то есть 1|1|n например не можем сделать.

Answer 1

[Mercury13]

Если число 3 задано жёстко, проще всего тройной цикл

для i = [0..n—2)
  для j = [i+1..n−1)
    для k = [j+1..n)

Если нежёстко, то получаем такое.

Изначально массив инициализирован числами 0, 1, 2. Шагом является вот такая сложная операция.
Добавляем единицу к последнему элементу. Если он больше n−1, то крутим вторую итерацию цикла — добавляем 1 к предпоследнему, если он больше n−2, крутим третью.
Если цикл прошёл весь массив и так и не закончился — перебор окончен. Иначе идём по массиву вперёд и заполняем хвост числами a[i]+1, a[i]+2…

Comments

[Selbi]

Хоть и все отвечающие дали один и тот же ответ, но Ваш весьма содержательный и появилось представление как решать такие задачи. Благодарю! ) Если знаете, можете подсказать что можно почитать по теме, кроме как комбинаторики? Имею ввиду с уклоном на программирование.

[Mercury13]

selbi, У меня чуть более развёрнутый — в смысле, как писать, ексли вдруг 3 придётся заменять на 2 или 4.

Как подобные алгоритмы делать? Представьте себе счётчик (автомобильный или электроэнергии) на n колёс. Сможете сделать, чтобы он считал от 0000 до 9999? А теперь модифицируем этот алгоритм под наши нужды.

[Selbi]

Mercury13, Да, этим и развернут ) и это как раз и надо было ) Думала сама додумаюсь как делать если 4 или 5 элементов надо, главное суть понять, а Вы рассказали и вроде все получилось теперь. Еще раз спасибо! Над счетчиком подумаю как время будет )

Answer 2

[Денис Загаевский]

Тройной вложенный цикл. i от 0 до n - 3, j от i+1 до n-2, k от j+1 до n-1.
i, j, k будут индексами.

Answer 3

[vyrkmod]

$max = count($array);
for($i = 0; $i <= $max - 2; $i++) {
    for($j = $i + 1; $j <= $max - 1; $j++) {
        for($k = $j + 1; $k <= $max; $k++) {
            echo($array[$i] . "|" . $array[$j] . "|" . $array[$k] . "\n");
        }
    }
}