Алгоритм для генерации всех перестановок разных размеров группы целых чисел?

Question

Предположим, у меня есть массив целых чисел, например [3,4,2,7,8,5]

Как бы я мог сгенерировать переменные по размеру из этого массива?

Как получить ВСЕ возможные пары из 2 или ВСЕ возможные наборы из 3? из 4?

Я хотел бы иметь возможность сделать это очень быстро.

Answer 1

Для языкового агностического подхода из первых принципов: перечислите все подмножества размера k (для k = 2, ..., n, где n - размер массива). Статья Википедии о комбинациях содержит раздел о своих enumeration. Для каждого перечислимого подмножества используйте Johnson-Trotter algorithm для перечисления его перестановок. Общее количество таких перестановок очень велико. Например, всего 10 предметов - 9 864 090

Многие языки будут иметь библиотечную поддержку. Например, это тривиальное программирование в Python (с использованием его модуля itertools). Здесь генератор для получения таких перестановок:

import itertools 

def allPermutations(items): 
    n = len(items) 
    for k in range(2,n+1): 
     for combo in itertools.combinations(items,k): 
      for perm in itertools.permutations(combo): 
       yield perm 

Например, list(allPermutations([3,4,2,7,8,5])) вычисляется в список 1950 таких перестановок, взятых из [3,4,2,7,8,5].

Answer 2

Вы можете использовать любой алгоритм (например, известный Narayana algorithm) для генерации всех перестановок размера N.

Теперь, если в этой общей последовательности перестановок вы считаете только перестановок с префиксом (а , A ..., а _к), где < < ... < a _k, то хвостовые части всех таких перестановок образуют последовательность всех возможных перестановок длины N - k.

Таким образом, делая один проход через все перестановки длины N, вы можете сгенерировать все перестановки длины N и короче.

Вот что реализация С ++ может выглядеть

#include <iostream> 
#include <algorithm> 
#include <iterator> 

int main() 
{ 
    int a[] = { 2, 3, 4, 5, 7, 8 }; 

    do 
    { 
    for (auto ite = std::begin(a); ite != std::end(a); ++ite) 
     if (std::is_sorted(std::begin(a), ite)) 
     { 
     std::copy(ite, std::end(a), std::ostream_iterator<int>(std::cout)); 
     std::cout << std::endl; 
     } 

    } while (std::next_permutation(std::begin(a), std::end(a))); 
} 

(я взял на себя смелость предварительной сортировки ваш входной набор.)

выше, очевидно, не является оптимальным, так как последовательных вызовах std::is_sorted внутри цикл for будет повторно повторять/проверять, что уже было проверено на предыдущей итерации. Но опять же эта реализация предназначена только для иллюстративных целей.

Теперь возникает вопрос, довольны ли вы порядком, в котором эти перестановки сгенерированы. Приведенный выше подход не группирует их по длине.

---

В качестве альтернативы, вы можете перебирать all possible combinations, а затем просто генерировать все возможные перестановки для каждой комбинации.