Algorithme C ++ qui renvoie toutes les combinaisons possibles de nombres donnés - c ++, algorithme, récursivité

J'essaie de trouver toutes les combinaisons possibles de nombres.

par exemple: Entrée 1 2 3 4 5

Sortie 1, 2 3 4 5 21 31 32 41 42 43 51 52 53 54 321, 421, 431, 432, 521, 531, 532 541, 542 543 4321, 5321, 5421, 5431, 5432, 54321

(chaque nombre devrait être cet ordre - du plus grand au plus bas)

J'ai un tableau trié. J'essaie d'écrire ces chiffres, cela fonctionne parfaitement, mais l'entrée avec plusieurs numéros identiques, comme 3 3 2 2 1, ne fonctionne pas bien.

La mauvaise chose est que cela nécessite de la récursivité.

mon algorithme de base ressemble à ceci: (c'est plus compliqué mais c'est une structure de base)

extract(arrWithNumbers, PrintingArray) {

For(i = 0; 0 < Numbers in array; i++) {
if (numbers == i + 1) print(PrintingArray);
PrintingArray[i] = arrWithNumbers[i];
extract(arrWithNumbers, PrintingArray);
}
}

Existe-t-il un algorithme connu qui puisse m'aider?

C’est non seulement de trouver toutes les combinaisons possibles en utilisant

Merci pour votre temps et votre aide.

Réponses:

1 pour la réponse № 1

Exemple de code:

#include <stdio.h>

int next_combination(size_t *I, size_t k, size_t n)
{
size_t i, j;
i = k-1;                            /* find next element to increment */
while(I[i] == (n-k+i)){
--i;
if(i == (size_t)-1){            /* if done */
for(i = 0; i < k;  i++)     /*  return with initial combination */
I[i] = i;
return(0);
}
}
I[i] += 1;                          /* increment element */
for(j = i+1; j < k; j++)            /* create increasing string */
I[j] = I[i]+j-i;
return(1);                          /* return with new combination */
}

int main(int argc, char **argv)
{
int    A[5] = {5, 4, 3, 2, 1};
size_t I[5];
size_t i, k, n;
n = sizeof(A)/sizeof(A[0]);         /* n things */
for(k = 1; k <= n; k++){            /* n things k at a time */
for(i = 0; i < k;  i++)         /* create initial combination */
I[i] = i;
do{                             /* display combinations */
for(i = 0; i < k; i++)
printf("%2d", A[I[i]]);
printf("n");
}
while(next_combination(I, k, n));
}
return(0);
}

---

0 pour la réponse № 2

cela peut être fait avec un peu de magie:

std::vector<int> vec {5, 4, 3, 2, 1};
int n = vec.size();
int cap = 1 << n;
for( int i=1; i<cap; ++i )
{
for( int j=0; j<n; ++j )
{
if( i & (1<<j) ) cout << vec[j] << " ";
}
cout << "n";
}

passer de 1 à 2 ^ n, et laisser les bits représenter si le nombre est présent ou non

---