C ++ Newbie braucht hilft zum Drucken Kombination von ganzen Zahlen

Question

Angenommen, ich bin gegeben:

1. Eine Reihe von ganzen Zahlen iRange (das heißt von 1 bis iRange) und
2. Eine gewünschte Anzahl von Kombinationen

Ich mag die Anzahl aller möglichen Kombinationen zu finden und all diese Kombinationen ausdrucken.

Zum Beispiel:

Da : iRange = 5 und n = 3

Dann ist die Anzahl von Kombinationen ist iRange! / ((iRange!-n!)*n!) = 5! / (5-3)! * 3! = 10 Kombinationen, und der Ausgang ist:

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

Ein weiteres Beispiel:

Da : iRange = 4 und n = 2

Dann ist die Anzahl von Kombinationen ist iRange! / ((iRange!-n!)*n!) = 4! / (4-2)! * 2! = 6 Kombinationen, und der Ausgang ist:

12 - 13 - 14 - 23 - 24 - 34

Mein Versuch, so weit ist:

#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;   
}

Mein Problem: Der Teil meines Codes auf den Druck von den Kombinationen im Zusammenhang funktioniert nur für n = 2, iRange = 4 und ich kann es in der Regel nicht funktioniert, das heißt, für jeden n und iRange.

Answer 1

Hier ist der Code bearbeitet: D: D mit einer rekursive Lösung:

#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

Ihre Lösung wird immer nur für n = 2 arbeiten. Denken Sie über eine Anordnung (Kämme) mit n Ganzzahlen verwenden, dann wird die Schleife das letzte Element in dem Array tick up. Wenn das Element max Aktualisierung erreicht dann kämmen [n-2] Artikel und stellen Sie das letzte Element auf den vorherigen Wert +1.

Im Grunde wie eine Uhr funktioniert, aber Sie müssen Logik finden, was zu uptick und was der nächste Minimalwert ist.

Answer 3

Sieht aus wie ein gutes Problem für Rekursion.

Definieren Sie eine Funktion f(prefix, iMin, iMax, n), die alle Kombinationen von n Ziffern druckt im Bereich [iMin, iMax] und gibt die Gesamtzahl der Kombinationen. Für n = 1, es sollte jede Ziffer von iMin iMax und zurück iMax - iMin + 1 drucken.

Für Ihre iRange = 5 und n = 3 Fall, rufen Sie f("", 1, 5, 3). Die Ausgabe sollte 123 - 124 - 125 - 134 - 135 - 145 - 234 - 235 - 245 - 345 werden.

Hinweis, dass die erste Gruppe von Ausgängen wird einfach auf die Ausgänge des 1 Präfix f("", 2, 5, 2), d.h. f("1", 2, 5, 2), gefolgt von f("2", 3, 5, 2) und f("3", 4, 5, 2). Sehen Sie, wie Sie das mit einer Schleife tun würde. Zwischen diesem, der Fall für n = 1 oben, und Fallen für schlechte Eingänge (am besten, wenn sie nichts drucken und 0 zurück, sollte es die Schleife vereinfachen), sollten Sie in der Lage seines f() schreiben zu können.

Ich bin zu stoppen kurz, weil dies wie eine Hausaufgabe sieht. Ist das genug, um Sie, um loszulegen?

EDIT: Nur für kichert, ich habe eine Python-Version geschrieben. Python hat eine einfachere Zeit-Sets und Listen von Dingen zu werfen um und bleibt lesbar.

#!/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])

Beachten Sie, dass Combos() nicht über die Arten der Elemente in der Liste items schert.

Answer 4

Hier ist ein Beispiel einer einfachen rekursiven Lösung. Ich glaube, dass es eine optimale Umsetzung liegt vor, wenn Sie die Rekursion mit Zyklen ersetzen. Es könnte Ihre Hausaufgaben:)

#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

Das ist meine C ++ Funktion mit verschiedenen Schnittstelle (basierend auf M. :: set), aber die gleiche Aufgabe auszuführen:

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;
}