Перебирая все комбинации

Question

Я пытаюсь запрограммировать игру для нескольких игроков на Java.

Мне нужно создать список всех комбинаций и сохранить их в массиве.

Если вошли 2 игрокав начале игры используются следующие комбинации: p1, p2 и p2, p1 (позиции важны)

, а если в игру вошли 3 игрока, это следующие комбинации: p1, p2, p3;р1, р3, р2;р2, р1, р3;р2, р3, р1;p3, p1, p2 и p3, p2, p1

На самом деле мне нужен избыточный массив: если вошли 3 игрока, мне нужно заранее комбинации 3 И комбинации каждой возможной пары p1,р2, р3;р1, р3, р2;р2, р1, р3;р2, р3, р1;p3, p1, p2 и p3, p2, p1 и p1, p2 и p2, p1 и p1, p3 и p3, p1 и p2, p3 и p3, p2)

Многие игроки (отредактировано: до 8игроки) могут одновременно войти в один и тот же раунд игры.(ИЗМЕНЕНО: существует до 32 групп, но это не важно, потому что группы независимы)

Существует ли быстрый, короткий и простой способ создать этот массив комбинаций для n игроков?

Предусмотрено и приемлемо рекурсивное решение.

Большое спасибо

PS

Моя постоянная идея состоит в том, чтобы разделить группу на 2, выбранную пару и остальную частьигроки.Разделенные пары выбираются с помощью 2 циклов FOR, а остальные - с помощью третьего.Если есть 2 игрока, нет «отдыха». Если есть 3 игрока, 2 FOR выберут позиции пары, а остальные получат остальные. Затем остальные упорядочиваются с использованием той же процедуры разделения.стать реальным? как? это будет эффективно? еще раз спасибо.

Answer 1

Число перестановок размера n равно n !, которое растет в геометрической прогрессии. Например, число всех перестановок из 20 элементов составляет 2432902008176640000 (~ 2,43290201 × 10 ^ 18), довольно большое число.

Как вы правильно догадались, существует рекурсивный алгоритм для генерации всех перестановок, но он совершенно неэффективен как во времени, так и в пространстве по причинам, перечисленным выше.

Однако, если ваша задача генерирует случайную перестановку, эффективный алгоритм существует: Fisher-Yates shuffle . Это требует времени O (n) (при условии, что вы можете сгенерировать случайное целое число в O (1)) и O (1) дополнительной памяти.

Answer 2

Вы знаете количество записей в каждом массиве. Для массива со всеми игроками это 256! Это возможности для первой записи в массиве, 255 для следующей и так далее. 256! это достаточно большое число, что мой калькулятор не может справиться с этим. Даже для 170 игроков размер массива будет 1,3e241. Даже на 64-битном компьютере у вас есть только 1.8e19 адресуемых байтов. Это в основном означает, что вам нужно переосмыслить свой подход.