C ++ 초보자 요구는 정수의 조합 인쇄에 도움이됩니다.
-
18-09-2019 - |
문제
내가 주어 졌다고 가정합니다.
- 다양한 정수
iRange
(즉,1
까지iRange
) 그리고 - 원하는 수의 조합
가능한 모든 조합의 수를 찾고이 모든 조합을 인쇄하고 싶습니다.
예를 들어:
주어진: iRange = 5
그리고 n = 3
그런 다음 조합 수가 있습니다 iRange! / ((iRange!-n!)*n!) = 5! / (5-3)! * 3! = 10
조합 및 출력은 다음과 같습니다.
123 - 124 - 125 - 134 - 135 - 145 - 234 - 235 - 245 - 345
또 다른 예:
주어진: iRange = 4
그리고 n = 2
그런 다음 조합 수가 있습니다 iRange! / ((iRange!-n!)*n!) = 4! / (4-2)! * 2! = 6
조합 및 출력은 다음과 같습니다.
12 - 13 - 14 - 23 - 24 - 34
지금까지의 시도는 다음과 같습니다.
#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;
}
내 문제:조합 인쇄와 관련된 내 코드의 일부는 n = 2, iRange = 4
그리고 나는 그것이 일반적으로 작동하게 할 수 없습니다. n
그리고 iRange
.
해결책
다음은 코드 편집입니다. D : D with a 재귀 해결책:
#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;
}
다른 팁
솔루션은 n = 2에만 작동합니다. n int와 함께 배열 (Combs)을 사용하는 방법을 생각하면 루프가 배열에서 마지막 항목을 선택합니다. 해당 항목이 최대 업데이트에 도달하면 [N-2] 항목을 빗고 마지막 항목을 이전 값 +1로 설정하십시오.
기본적으로 시계처럼 작동하지만 다음과 같은 최소 값이 무엇인지 찾기 위해 논리가 필요합니다.
재귀에게는 좋은 문제처럼 보입니다.
함수를 정의하십시오 f(prefix, iMin, iMax, n)
, 그것은 모든 조합을 인쇄합니다 n
범위의 숫자 [iMin
, iMax
] 총 조합 수를 반환합니다. 을 위한 n
= 1, 모든 숫자를 인쇄해야합니다 iMin
에게 iMax
그리고 반환 iMax - iMin + 1
.
당신을 위해 iRange = 5
그리고 n = 3
케이스, 당신은 전화합니다 f("", 1, 5, 3)
. 출력이 있어야합니다 123 - 124 - 125 - 134 - 135 - 145 - 234 - 235 - 245 - 345
.
첫 번째 출력 그룹은 간단합니다 1
출력에 접두사 f("", 2, 5, 2)
, 즉 f("1", 2, 5, 2)
, 그 뒤에 f("2", 3, 5, 2)
그리고 f("3", 4, 5, 2)
. 루프로 어떻게 할 것인지 확인하십시오. 이것 사이에서, 사례 n
= 1 위의 입력에 대한 트랩 (아무것도 인쇄하지 않고 0을 반환하면 루프를 단순화해야합니다). 글을 쓸 수 있어야합니다. f()
.
이것은 숙제 할당처럼 보이기 때문에 짧게 멈추고 있습니다. 이것이 당신을 시작하기에 충분합니까?
편집 : Giggles를 위해서는 Python 버전을 썼습니다. Python은 세트와 사물 목록을 던지고 읽기 쉬운 상태를 유지하는 데 더 쉬운 시간을 보냅니다.
#!/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])
주목하십시오 Combos()
항목의 유형에 신경 쓰지 않습니다. items
목록.
다음은 일반 재귀 솔루션의 예입니다. 재귀를 사이클로 바꾸면 더 최적의 구현이 존재한다고 생각합니다. 그것은 당신의 숙제 일 수 있습니다 :)
#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;
}
이것은 인터페이스가 다른 인터페이스 (sts :: set에 따라)를 가진 C ++ 함수이지만 동일한 작업을 수행합니다.
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;
}