C ++ Débutant besoin aide pour les combinaisons d'impression d'entiers

Question

Si je me donne:

1. Une gamme d'entiers iRange (à savoir à partir de 1 jusqu'à iRange) et
2. Un certain nombre de combinaisons souhaitée

Je veux trouver le nombre de toutes les combinaisons possibles et imprimer toutes ces combinaisons.

Par exemple:

Vu : iRange = 5 et n = 3

Ensuite, le nombre de combinaisons est des combinaisons iRange! / ((iRange!-n!)*n!) = 5! / (5-3)! * 3! = 10, et la sortie est:

123 - 124 - 125 - 134 - 135 - 145 - 234 - 235 - 245 - 345

Un autre exemple:

Vu : iRange = 4 et n = 2

Ensuite, le nombre de combinaisons est des combinaisons iRange! / ((iRange!-n!)*n!) = 4! / (4-2)! * 2! = 6, et la sortie est:

12 - 13 - 14 - 23 - 24 - 34

Ma tentative à ce jour est:

#include <iostream>
using namespace std;

int iRange= 0;
int iN=0;

int fact(int n)
{
    if ( n<1)
        return 1;
    else
    return fact(n-1)*n;
}

void print_combinations(int n, int iMxM)
{
    int iBigSetFact=fact(iMxM);
    int iDiffFact=fact(iMxM-n);
    int iSmallSetFact=fact(n);
    int iNoTotComb = (iBigSetFact/(iDiffFact*iSmallSetFact));
    cout<<"The number of possible combinations is: "<<iNoTotComb<<endl;
    cout<<" and these combinations are the following: "<<endl;


    int i, j, k;
    for (i = 0; i < iMxM - 1; i++)
    {
        for (j = i + 1; j < iMxM ; j++)
        {
            //for (k = j + 1; k < iMxM; k++)
                cout<<i+1<<j+1<<endl;
        }
    }
}

int main()
{
    cout<<"Please give the range (max) within which the combinations are to be found: "<<endl;
    cin>>iRange;
    cout<<"Please give the desired number of combinations: "<<endl; 
    cin>>iN;
    print_combinations(iN,iRange);
    return 0;   
}

Mon problème: La partie de mon code lié à l'impression des combinaisons ne fonctionne que pour n = 2, iRange = 4 et je ne peux pas le faire fonctionner en général, à savoir, pour tout n et iRange.

Answer 1

Voici votre code édité: D: D avec un récursive Solution:

#include <iostream>

int iRange=0;   
int iN=0;           //Number of items taken from iRange, for which u want to print out the combinations
int iTotalCombs=0;
int* pTheRange;
int* pTempRange;

int find_factorial(int n)
{
    if ( n<1)
        return 1;
    else
    return find_factorial(n-1)*n;
}

//--->Here is another solution:
void print_out_combinations(int *P, int K, int n_i) 
{
    if (K == 0)
    {
        for (int j =iN;j>0;j--)
        std::cout<<P[j]<<" ";
        std::cout<<std::endl;
    }
    else
        for (int i = n_i; i < iRange; i++) 
        {
            P[K] = pTheRange[i];
            print_out_combinations(P, K-1, i+1);
        }
}
//Here ends the solution...

int main() 
{
    std::cout<<"Give the set of items -iRange- = ";
    std::cin>>iRange;
    std::cout<<"Give the items # -iN- of iRange for which the combinations will be created = ";
    std::cin>>iN;

    pTheRange = new int[iRange];
    for (int i = 0;i<iRange;i++)
    {
        pTheRange[i]=i+1;
    }
    pTempRange = new int[iN];

    iTotalCombs = (find_factorial(iRange)/(find_factorial(iRange-iN)*find_factorial(iN)));

    std::cout<<"The number of possible combinations is: "<<iTotalCombs<<std::endl;
    std::cout<<"i.e.the combinations of "<<iN<<" elements drawn from a set of size "<<iRange<<" are: "<<std::endl;
    print_out_combinations(pTempRange, iN, 0);
    return 0;
}

Answer 2

Votre solution ne fonctionnera jamais pour n = 2. Pensez à utiliser un tableau (peignes) avec n ints, alors la boucle cochera le dernier élément du tableau. Lorsque cet élément atteint mise à jour max puis peigne [n-2] et un objet fixé sur le dernier élément à la valeur précédente 1.

En gros travail comme une horloge, mais vous avez besoin de logique pour trouver quoi et légère hausse ce que la prochaine valeur minimale est.

Answer 3

On dirait un bon problème pour récursivité.

Définir une f(prefix, iMin, iMax, n) fonction, qui imprime toutes les combinaisons de chiffres n dans l'intervalle [iMin, iMax] et renvoie le nombre total de combinaisons. Pour n = 1, il faut imprimer tous les chiffres de iMin à iMax et retour iMax - iMin + 1.

Pour votre iRange = 5 et cas de n = 3, vous appelez f("", 1, 5, 3). La sortie doit être 123 - 124 - 125 - 134 - 135 - 145 - 234 - 235 - 245 - 345.

Notez que le premier groupe de sorties sont simplement 1 préfixé sur les sorties des f("", 2, 5, 2), à savoir f("1", 2, 5, 2), suivie par f("2", 3, 5, 2) et f("3", 4, 5, 2). Voyez comment vous le faire avec une boucle. Entre cela, le cas pour n = 1 ci-dessus, et des pièges pour les mauvaises entrées (mieux s'ils impriment rien et retourner 0, il devrait simplifier votre boucle), vous devriez être en mesure d'écrire f().

J'arrête court parce que cela ressemble à un devoir. Est-ce assez pour vous commencer?

EDIT: Juste pour rire, je l'ai écrit une version Python. Python a un temps plus facile de jeter autour des jeux et des listes de choses et de rester lisible.

#!/usr/bin/env python

def Combos(items, n):
    if n <= 0 or len(items) == 0:
        return []
    if n == 1:
        return [[x] for x in items]
    result = []
    for k in range(len(items) - n + 1):
        for s in Combos(items[k+1:], n - 1):
            result.append([items[k]] + s)
    return result

comb = Combos([str(x) for x in range(1, 6)], 3)
print len(comb), " - ".join(["".join(c) for c in comb])

Notez que Combos() ne se soucie pas des types des éléments dans la liste de items.

Answer 4

Voici un exemple d'une solution récursive simple. Je crois qu'il existe une application plus optimale si vous remplacez récursion avec des cycles. Il pourrait être vos devoirs:)

#include <stdio.h>

const int iRange = 9;
const int n = 4;


// A more efficient way to calculate binomial coefficient, in my opinion
int Cnm(int n, int m)
{
    int i;
    int result = 1;

    for (i = m + 1; i <= n; ++i)
        result *= i;

    for (i = n - m; i > 1; --i)
        result /= i;

    return result;
}


print_digits(int *digits)
{
    int i;
    for (i = 0; i < n; ++i) {
        printf("%d", digits[i]);
    }
    printf("\n");
}

void plus_one(int *digits, int index)
{
    int i;

    // Increment current digit
    ++digits[index];

    // If it is the leftmost digit, run to the right, setup all the others
    if (index == 0) {
        for (i = 1; i < n; ++i)
            digits[i] = digits[i-1] + 1;
    }
    // step back by one digit recursively
    else if (digits[index] > iRange) {
        plus_one(digits, index - 1);
    }
    // otherwise run to the right, setting up other digits, and break the recursion once a digit exceeds iRange
    else {
        for (i = index + 1; i < n; ++i) {
            digits[i] = digits[i-1] + 1;

            if (digits[i] > iRange) {
                plus_one(digits, i - 1);
                break;
            }
        }
    }
}

int main()
{
    int i;
    int digits[n];

    for (i = 0; i < n; ++i) {
        digits[i] = i + 1;
    }

    printf("%d\n\n", Cnm(iRange, n));

    // *** This loop has been updated ***
    while (digits[0] <= iRange - n + 1) {
        print_digits(digits);
        plus_one(digits, n - 1);
    }

    return 0;
}

Answer 5

Ceci est mon fonction C ++ avec une interface différente (en fonction de m :: set), mais effectuer la même tâche:

typedef std::set<int> NumbersSet;
typedef std::set<NumbersSet> CombinationsSet;

CombinationsSet MakeCombinations(const NumbersSet& numbers, int count)
{
  CombinationsSet result;

  if (!count) throw std::exception();

  if (count == numbers.size())
  {
    result.insert(NumbersSet(numbers.begin(), numbers.end()));
    return result;
  }

  // combinations with 1 element
  if (!(count - 1) || (numbers.size() <= 1))
  {
    for (auto number = numbers.begin(); number != numbers.end(); ++number)
    {
      NumbersSet single_combination;
      single_combination.insert(*number);
      result.insert(single_combination);
    }
    return result;
  }

  // Combinations with (count - 1) without current number
  int first_num = *numbers.begin();
  NumbersSet truncated_numbers = numbers;
  truncated_numbers.erase(first_num);
  CombinationsSet subcombinations = MakeCombinations(truncated_numbers, count - 1);

  for (auto subcombination = subcombinations.begin(); subcombination != subcombinations.end(); ++subcombination)
  {
    NumbersSet cmb = *subcombination;
    // Add current number
    cmb.insert(first_num);
    result.insert(cmb);
  }

  // Combinations with (count) without current number
  subcombinations = MakeCombinations(truncated_numbers, count);
  result.insert(subcombinations.begin(), subcombinations.end());

  return result;
}