n個の数{1,2,3,...,n}を与え,その中から任意の2つの異なるk個の数を選択し,すべての可能な組合せを出力する
1496 ワード
問題のように、与えられたnは5であり、このn個の数は{1,2,3,4,5}であり、与えられたkは2であり、
すべての可能な組み合わせは次のとおりです.
{1,2}、{1,3}、{1,4}、{1,5}、{2,3}、{2,4}、{2,5}、{3,4}、{3,5}、{4,5}
そして、私たちは常にこのような順序ですべての可能性を探しています.では、この論理プログラミングに従って実現するにはどうすればいいのでしょうか.
上のシーケンスから,隣接する2つの数には一定の関係があることが分かった.
例えば1で始まる組み合わせでは、2番目の数字がインクリメントされ、すべての組み合わせで{1,...,k}が1番目に間違いないことがわかる
組み合わせ、{n-k+1,...,n}は必ず最後の組み合わせであり、n-k+1で始まる組み合わせも1つしかない.すなわち、この組み合わせフラグ
探しているうちに終わりました.だから、最初の組み合わせから始めて、最後の組み合わせと比較して、すべての組み合わせを循環して見つけることができます.
すべての可能な組み合わせは次のとおりです.
{1,2}、{1,3}、{1,4}、{1,5}、{2,3}、{2,4}、{2,5}、{3,4}、{3,5}、{4,5}
そして、私たちは常にこのような順序ですべての可能性を探しています.では、この論理プログラミングに従って実現するにはどうすればいいのでしょうか.
上のシーケンスから,隣接する2つの数には一定の関係があることが分かった.
例えば1で始まる組み合わせでは、2番目の数字がインクリメントされ、すべての組み合わせで{1,...,k}が1番目に間違いないことがわかる
組み合わせ、{n-k+1,...,n}は必ず最後の組み合わせであり、n-k+1で始まる組み合わせも1つしかない.すなわち、この組み合わせフラグ
探しているうちに終わりました.だから、最初の組み合わせから始めて、最後の組み合わせと比較して、すべての組み合わせを循環して見つけることができます.
/***************************************************
*filename: AllChose.c
*date: 2014/3/30
*author: Yuqiang HAN
*version: v1.0
***************************************************/
#include
#define MAX 100
/*************************
*function: AllChose
*input: n
* k
*return none
**************************/
void AllChose(int n, int k)
{
if(n < k || n <= 0 || k <= 0)
{
return;
}
int i;
int j;
int count = 1;
int arr[MAX];
int index[MAX];
for(i = 1; i <= k; i++)
{
arr[i] = i;
index[i] = n-k+i;
}
while(true)
{
printf(" #count :
", count++);
for(i = 1; i <=k; i++)
{
printf("%d ",arr[i]);
}
printf("
");
if(arr[1] == n-k+1) //
{
break;
}
for(i = k; i >= 1; i--)
{
if(arr[i] < index[i])
{
arr[i]++;
for(j = i+1; j <= k; j++)
{
arr[j] = arr[j-1] + 1;
}
break;
}
}
}
}