Комбинации с несколькими группами

Question

Как бы вы программно перечисляли все возможные уникальные комбинации набора чисел в несколько групп?

Например, если у меня есть набор {1,2,3,4,5,6,7,8,9,10}, и я хочу 3 группы размером 3, 3, 2, одно из возможных подмножеств будет {[1, 2, 3], [4, 5, 6], [7, 8]}

это эквивалентно {[3, 2, 1], [6, 5, 4], [ 7, 8]} и будет рассматриваться как дубликат

, тогда как {[4, 2, 3], [1, 5, 6], [7, 8]} будут рассмотрены различные подмножества

Очевидно Я ищу наиболее эффективный и практичный способ сделать это. Я буду работать с довольно большим N, поэтому алгоритм должен быть масштабируемым.

Answer 1

Еще один способ подумать об этой проблеме - это перестановки мультимножества {1, 1, 1, 2, 2, 2, 3, 3}. Если такая перестановка p имеет значение i в позиции j, это означает, что элемент j из вашего исходного набора должен быть помещен в раздел i.

Использование, например, ++ шаблон C next_permutation вы можете перечислить эти перестановки следующим образом:

int main() { 
    int a[] = { 0, 0, 0, 1, 1, 1, 2, 2 }; 
    do { 
    // Here a[j] == i means element j of your set goes in partition i. 
    // Do whatever you want to do with the permutations generated this way. 
    } while (std::next_permutation(a, a + 8)); 
} 

Результат будет содержать 10/(3 3 2!!) = 560 различных комбинаций!. Демо-код этого кода, включая вывод, похожий на нотацию, используемую в вашем заявлении о проблеме, - available at ideone. Вы можете посмотреть the source code, если вы хотите знать, как next_permutation реализован для gcc, но только так, если лицензия вашего целевого проекта позволяет копировать этот код.