Найти все возможные массивы размера n, построенные со всеми возможными комбинациями элементов из другого массива во всех возможных порядках?
Для массива A произвольной длины n я хотел бы заполнить массив B размером x x m всей комбинацией элементов из A, которая включает все возможные порядки этих элементов. Например, если A = {1, 2, 3} и m = 2, я хотел бы получить B как:
11
12
13
21
22
23
31
32
33
Какой эффективный способ сделать это в C / C ++? Спасибо!
РЕДАКТИРОВАТЬ: Вот то, что я понял, чтобы работать (данные находятся внутри гребней класса, который в основном матричный класс с некоторыми дополнительными приемами):
void combs::setCombs (int arr[], int n, int m) {
int z, tmp, repeat;
int max = (int (pow(double (n), double( m ))));
for (int i = 0; i < m; i++) {
z = 0;
repeat = int (pow( double (n), double (i)));
for (int j = 0; j < repeat; j++) {
for (int k = 0; k < n; k ++) {
for (int p = 0; p < max/(n*repeat); p ++) {
cout << arr[k] << endl;
data[z*ROWS + i] = arr[k];
z++;
}
}
}
}
}
Решение
Как упомянул @Joachim Pileborg, вашему вопросу не хватает параметров.
Но допустим, вы могли бы гарантировать, что передавали мне вектор сортированных уникальных целых. Тогда эта грубая сила была бы возможна:
std::vector< std::string > Combo( const std::vector< char >& source, int m )
{
std::vector< std::vector< char >::const_iterator > digits( length, source.cbegin() );
std::vector< std::string > result( source.size() * m );
for( int i = 0; i < result.size(); i++ )
{
for( int j = 0; j < m; j++ )
{
result[i] += *(digits[j]);
}
for( int j = digits.size() - 1; j >= 0; j-- )
{
++digits[j];
if( digits[j] == source.cend() )
{
digits[j] = source.cbegin();
}
else
{
break;
}
}
}
return result;
}
Другие решения
То, что вы описываете, звучит как частичные перестановки, а не комбинации.
Если вы используете c ++, то рекомендуется использовать векторы, потому что векторы могут сообщить вам свой размер и освободить собственную память. Реализация с векторами будет выглядеть следующим образом:
vector<vector<int> > partialPermutations(vector<int> &A,int m){
int i,i2,t,n=A.size(),total=1;
for(i=0;i<m;i++) total*=n;
vector<vector<int> > result;
for(i=0;i<total;i++){
result.push_back(vector<int>());
t=i;
for(i2=0;i2<m;i2++){
result[i].push_back(A[t%n]);
t/=n;
}
}
return result;
}
int main() {
vector<int> A;
int total,i,i2;
for(i=1;i<=4;i++) A.push_back(i);
vector<vector<int> > re=partialPermutations(A,2);
for(i=0;i<re.size();i++){
for(i2=0;i2<2;i2++)
cout<<re[i][i2]<<" ";
cout<<endl;
}
return 0;
}
Если вы все еще хотите использовать массивы, код будет выглядеть следующим образом:
int** partialPermutations(int*A,int n,int m,int &total){
int i,i2,t;
total=1;
for(i=0;i<m;i++) total*=n;
int **result=new int*[total];
for(i=0;i<total;i++){
t=i;
result[i]=new int[m];
for(i2=0;i2<m;i2++){
result[i][i2]=A[t%n];
t/=n;
}
}
return result;
}
int main() {
int A[]={1,2,3,4};
int total,i,i2;
int **re=partialPermutations(A,4,2,total);
for(i=0;i<total;i++){
for(i2=0;i2<2;i2++)
cout<<re[i][i2]<<" ";
cout<<endl;
}
//Cleanup
for(i=0;i<total;i++) delete[] re[i];
delete[] re;
return 0;
}
Обратите внимание, что используя массивы, мы должны восстановить размер результирующего массива (передавая total по ссылке), и мы должны освободить память впоследствии. Ничего этого не нужно с векторами.
#include<iostream>
using namespace std;
void printStrRec(string s,string ans,int k,int i)
{
if(i==k)
{
cout<<"\nAnswer : "<<ans<<endl;
}
else
{
for(int x=0;x<s.size();++x)
{
ans[i]=s[x];
printStrRec(s,ans,k,i+1);
}
}
}
void printStrings(string s,int k)
{
string ans;
for(int p=0;p<k;++p)
{
ans+="x";
}
printStrRec(s,ans,k,0);
}
int main()
{
int k;
string s;
cout<<"Enter the set : ";
cin>>s;
cout<<"\nEnter k : ";
cin>>k;
printStrings(s,k);
return 0;
}
Надеюсь, это поможет.
detector