Как можно заполнить вектор со всеми возможными комбинациями строк из n векторной длины в языке программирования C++

Question

У меня есть вектор из 100 строк и еще один пустой вектор, и я пытаюсь заполнить пустой вектор любой возможной комбинацией n строки из группы, состоящей из 100 (п = 1, 2, 3, ...)

Если п = 1, то вы получаете каждый уникальный вектор, состоящий из 1 строки (или все 100 строк в качестве векторов)

Если n = 2, вы получаете каждый уникальный вектор, состоящий из двух строк (или 100^2 вариаций)

C++ - это не мой родной язык.

У меня есть некоторые попытки до сих пор, и то, что я сделал бы в Zou_script (собственном собственном собственном), было бы присвоить каждой строке номер и затем переставить все возможные комбинации этих чисел, а затем ссылаться на отдельные строки через Vector [] для создания векторов.

Это кажется медленным и имеет недостаток элегантности, держа банк строчек в памяти может быть плохим, если банк струн был намного больше.

Я использовал std :: next_permutation, но у меня возникли проблемы с его элегантностью в сортировке векторов, состоящих из строк.

Как можно заполнить вектор со всеми возможными комбинациями строк из n векторной длины на языке программирования C++? < - Вопрос.

Может ли кто-нибудь помочь? Если вы не уверены или запуганы вопросом, то это нормально, чтобы перейти к следующему.

Update

мне удалось повторить технику в C++, но next_permutation значительно медленнее, потому что он не понимает, что не нужно вычислить весь вектор перестановок, только до п суммы.

Любой способ манипулировать next_permutation, чтобы вычислять только х элементов векторной перестановки?

Answer 1

Я задал этот вопрос, но я сделаю все возможное, чтобы дать ответ. На самом деле это хорошо изученный и часто задаваемый вопрос в C/C++.

«Как рассматривать перестановки группы из N элементов, r за раз?»

Существует множество способов решения проблемы. Одним из таких способов является создание вектора целых чисел, с которым можно сопоставить вектор ваших элементов.

Используя std :: next_permutation, вы можете сгенерировать список чисел (перестановки целочисленного вектора) и усечь количество предметов, которые вы рассматриваете. Затем этот список можно отсортировать с помощью векторных инструментов, удаленные дубликаты. Это даст вам список всех уникальных перестановок из N целых чисел, r за раз, для сопоставления с вашим вектором элемента.

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

for (int k = 0; k < linecount_of_integer_permutation_list; k++) 
{ 

    // insert code for calling up integer permutation list line 
    // and assigning that permutation to vector 

for (int i = 0; i < r; i++) 
{ 
file << element[intvec[r]]; // can put whatever delimiters you want/need 
} 
file << std::endl; 
intvec.clear(); 
// remember to clear vectors, or other flags depending on what you need 
} 

Это громоздко и очень медленно.

https://howardhinnant.github.io/combinations.html

Имеет некоторые очень хорошие идеи о том, как справиться с этой проблемой быстрее. Вышеупомянутое будет работать для небольших наборов, однако переход от малого к абсолютно неуправляемому очень быстрый в перестановках.

Благодарим за помощь. Это действительно интересный вопрос, но, по-видимому, он не нужен для приложений многих людей в программировании.