Генерация упорядоченного выбора с повторением назначенной длины записи
Я пишу функцию подражания unordered_tuple от мудрец комбинаторные функции доступно в питоне.
Однако он отличается тем, что используемый мной входной набор всегда [10, 9, 8, 7, 6], и меняется только количество входов (не больше 10).
Таким образом, желаемый выход для записи = 3 и для записи = 4,
unordered_tuples([10,9,8,7,6], 3)
[[6, 6, 6],
[6, 6, 7],
[6, 6, 8],
[6, 6, 9],
[6, 6, 10],
[6, 7, 7],
[6, 7, 8],
[6, 7, 9],
[6, 7, 10],
[6, 8, 8],
[6, 8, 9],
[6, 8, 10],
[6, 9, 9],
[6, 9, 10],
[6, 10, 10],
[7, 7, 7],
[7, 7, 8],
[7, 7, 9],
[7, 7, 10],
[7, 8, 8],
[7, 8, 9],
[7, 8, 10],
[7, 9, 9],
[7, 9, 10],
[7, 10, 10],
[8, 8, 8],
[8, 8, 9],
[8, 8, 10],
[8, 9, 9],
[8, 9, 10],
[8, 10, 10],
[9, 9, 9],
[9, 9, 10],
[9, 10, 10],
[10, 10, 10]]
unordered_tuples([10,9,8,7,6], 4)
[[6, 6, 6, 6],
[6, 6, 6, 7],
[6, 6, 6, 8],
[6, 6, 6, 9],
[6, 6, 6, 10],
[6, 6, 7, 7],
[6, 6, 7, 8],
[6, 6, 7, 9],
[6, 6, 7, 10],
[6, 6, 8, 8],
[6, 6, 8, 9],
[6, 6, 8, 10],
[6, 6, 9, 9],
[6, 6, 9, 10],
[6, 6, 10, 10],
[6, 7, 7, 7],
[6, 7, 7, 8],
[6, 7, 7, 9],
[6, 7, 7, 10],
[6, 7, 8, 8],
[6, 7, 8, 9],
[6, 7, 8, 10],
[6, 7, 9, 9],
[6, 7, 9, 10],
[6, 7, 10, 10],
[6, 8, 8, 8],
[6, 8, 8, 9],
[6, 8, 8, 10],
[6, 8, 9, 9],
[6, 8, 9, 10],
[6, 8, 10, 10],
[6, 9, 9, 9],
[6, 9, 9, 10],
[6, 9, 10, 10],
[6, 10, 10, 10],
[7, 7, 7, 7],
[7, 7, 7, 8],
[7, 7, 7, 9],
[7, 7, 7, 10],
[7, 7, 8, 8],
[7, 7, 8, 9],
[7, 7, 8, 10],
[7, 7, 9, 9],
[7, 7, 9, 10],
[7, 7, 10, 10],
[7, 8, 8, 8],
[7, 8, 8, 9],
[7, 8, 8, 10],
[7, 8, 9, 9],
[7, 8, 9, 10],
[7, 8, 10, 10],
[7, 9, 9, 9],
[7, 9, 9, 10],
[7, 9, 10, 10],
[7, 10, 10, 10],
[8, 8, 8, 8],
[8, 8, 8, 9],
[8, 8, 8, 10],
[8, 8, 9, 9],
[8, 8, 9, 10],
[8, 8, 10, 10],
[8, 9, 9, 9],
[8, 9, 9, 10],
[8, 9, 10, 10],
[8, 10, 10, 10],
[9, 9, 9, 9],
[9, 9, 9, 10],
[9, 9, 10, 10],
[9, 10, 10, 10],
[10, 10, 10, 10]]
и функция с ++, которую я написал, следует.
На самом деле я не опытный программист, и я просто пытался найти правильное решение, но оно работает правильно, но дает много повторяющихся решений.
Честно говоря, я написал эту функцию, но даже не знаю, что написал.
Я мог бы использовать set, но это было бы очень неэффективно, и я хочу знать правильное решение этой проблемы.
Кто-нибудь может починить так, чтобы он выдал вывод выше?
#include<iostream>
#include<string>
#include<cstdlib>
#include<vector>
using namespace std;
vector<vector<int> > ut(int);
int main(int argc, char** argv) {
int entry = atoi(argv[1]);
ut(entry);
return 1;
}
vector<vector<int> > ut(int entry) {
vector<vector<int> > ret;
int upper = 10;
vector<int> v(entry, upper);
ret.push_back(v);
typedef vector<int>::iterator iter_t;
iter_t it = v.begin();
int count=0;
int c = 0;
while(v.back() != 6) {
v = ret[count+c];
while(it != v.end()) {
--(*it);
++it;
ret.push_back(v);
++c;
}
it = v.begin();
c=0;
++count;
}for(int i=0; i<ret.size(); ++i) {
vector<int> tuple = ret[i];
for(int j=0; j<tuple.size(); ++j) {
cout << tuple[j] << ' ';
}
cout<<endl;
}
cout << endl;
return ret;
}
Решение
Смотри сюда:
vector<vector<int> > ret;
int upper = 10;
vector<int> v(entry, upper);
ret.push_back(v);
typedef vector<int>::iterator iter_t;
iter_t it = v.begin();
int count=0;
int c = 0;
while(v.back() != 6) {
v = ret[count+c];
while(it != v.end()) {
--(*it);
++it;
ret.push_back(v);
++c;
}
it = v.begin();
c=0;
++count;
}
Это просто страшно. (Я понимаю, что вы новичок; пожалуйста, поймите, что моя критика предназначена для того, чтобы помочь.) Обычно такого рода, если излишняя сложность не нужна и служит укрытием для ошибок. Заметить, что c а также it установлены до петля и в конце из цикла, и никогда не используется снова; мы можем установить их в начале цикла, и код будет короче и понятнее:
int count=0;
while(v.back() != 6) {
iter_t it = v.begin();
int c = 0;
v = ret[count+c];
while(it != v.end()) {
--(*it);
++it;
ret.push_back(v);
++c;
}
++count;
}
Теперь мы можем видеть, что c никогда не используется, кроме случаев, когда он равен нулю. (Посмотрите на оригинальный код, если вы мне не верите.) Но что еще хуже, it указывает на v, а потом v назначается новое значение. Так it вероятно указывает на мертвую память, и разыменование это вызывает неопределенное поведение. И непонятно, как этот код должен работать в любом случае.
Попробуй это:
vector<int> v(n,6);
vector<int>::iterator itr1;
do{
ret.push_back(v);
itr1 = v.begin();
while(++(*itr1)>10){
if(++itr1==v.end())
break;
}
for(vector<int>::iterator itr2 = v.begin(); itr2!=itr1; ++itr2)
*itr2 = *itr1;
}
while(itr1!=v.end());
Другие решения
Хорошее место для начала с проблемами перестановки рекурсия. Используя этот подход, чтобы построить все выходы длины 3, вы выбираете цифру из вашего набора [6, 7, 8, 9, 10], а затем добавьте к нему все выходы длины 2 с набором входных данных, ограниченным для начала с выбранной цифры. Так, если, например, ты выбрал 7ваш входной набор для первого рекурсивного вызова будет [ 7, 8, 9, 10], Т.е. рекурсивный вызов в этом случае будет добавлен к [ 7 ] все выводы длины 2 от входа [ 7, 8, 9, 10]
Программа, которая реализует эту идею, приведена ниже. Мне было бы интересно узнать, может ли кто-нибудь придумать нерекурсивное решение.
#include "stdafx.h"#include <iostream>
#include <vector>
typedef std::vector<int> intvec;
typedef std::vector<intvec> intvecs;
void GenerateUnOrderedIntVecs(
const int* remainingInput, int remainingInputLen,
const intvec& outputSoFar, int remainingOutputLen,
intvecs& output)
{
if (remainingOutputLen == 0) { // base case of recursion
output.push_back(outputSoFar);
return;
}
// For all digits in our input
for(int i=0; i<remainingInputLen; ++i) {
// Add the ith digit to our output so far
intvec outputSoFar2(outputSoFar);
outputSoFar2.push_back(remainingInput[i]);
// The recursion
GenerateUnOrderedIntVecs(
remainingInput + i, // input set constrained to start from chosen digit
remainingInputLen - i, // input set is shorter
outputSoFar2, // one digit longer than the parameter outputSoFar
remainingOutputLen -1, // so we need one digit less as we recurse
output);
}
}
int main(int argc, _TCHAR* argv[])
{
const int nToChooseFrom = 5;
const int nToChooose = 3;
const int input[nToChooseFrom] = { 6, 7, 8, 9, 10 }; // provide input in sorted order (or sort it!)
intvecs output;
GenerateUnOrderedIntVecs(
input, nToChooseFrom,
intvec(), nToChooose,
output);
for(intvecs::const_iterator i=output.begin(); i!=output.end(); ++i) {
std::cout << "[ ";
const intvec& unordered_tuple = *i;
for(intvec::const_iterator j = unordered_tuple.begin(); j!=unordered_tuple.end(); ++j) {
std::cout << *j << " ";
}
std::cout << "]\n";
}
return 0;
}
Кажется, это работает на обоих ваших примерах (но я проверил только первый тщательно). Если вы не видите, как это работает, читая код, хорошим подходом будет запустить его в отладчике (вот что мне нужно было сделать, чтобы заставить его работать! 🙂