組分けをプログラムで表現するには？？

質問

例えば３人の場合、{3}、{1，2}、{1，1，1}の３組に。
５人場合、{5}、{1，4}、{2，3}、{1，1，3}、{1，2，2}、{1，1，1，2}、{1，1，1，1，1}の７組に。
人数(n=)を入力すると上のような組分けと組がいくつ出来たかを表示させるプログラム(Cか出来ればmathematicaで)を作りたいのですが、なかなか作成できません。もしよろしければアルゴリズムなど何か少しでもアドバイス頂けると幸いです。（Cの場合、上のような{●，●}をどのように表すと良いでしょうか）

回答No.3

kapura · ベストアンサー

細かい話ですが、No.2の回答の最後の文で、@[n/2]-1ではなく@[n/2]+1ですね

以下はPerlのプログラムですが参考になるでしょうか。
# 間違いというか、たまたま動作しているところがあるかも

use strict;
my @all = ([[1]]); # 人数iの場合の全リスト (@iと表すとする) を第i-1要素にもつ配列 (@1で初期化)
my $n; # 人数
do {
print "Enter the number of people: "; # 人数nを入力してもらう
chomp($n = <STDIN>);
} while ($n !~ /^[1-9]\d*$/); # 入力が自然数でなければ再入力
if ($n == 1) { print "{1}\n"; exit } # nが1の場合は{1}を表示してプログラム終了 (@1は{1}のみ)
foreach my $i (2..$n) { # @iを求める (iは2からnまで順に変化させる)
my @tmp;
foreach (@{$all[$i-2]}) { push @tmp, [1, @$_] }
$all[$i-1] = \@tmp; # @iを@i-1の左端に1をつけ加えたもので初期化
if ($i > 3) { # 既知の@i-jを利用して、@iにリストを追加する (jは2から[i/2]まで順に変化させる)
foreach my $j (2..int($i/2)) {
foreach (@{$all[$i-1-$j]}) { # @i-jの全リストをチェックして、左端の数がj以上であれば
if ($_->[0] >= $j) { push @{$all[$i-1]}, [$j, @$_] }
}
}
}
push @{$all[$i-1]}, [$i]; # @iに{i}を追加する
}
foreach (@{$all[$n-1]}) { # @nの全リストを表示
print "{", join(", ", @$_), "}\n";
}
print scalar @{$all[$n-1]}, " lists\n";

回答No.5

BLUEPIXY

//一応作ってみました
/*
ある数ｎを分割する（正数の和で表す表し方の）数を求める
例
4:4,1+3,2+2,1+1+2,1+1+1の５通り
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

int *LIST; /* 数の組み合わせのリスト */
int COUNT=0; /* 組み合わせの件数 */
int LEVEL=-1; /* 分割するレベル */

void print (void){
int i;

printf("{ ");
for(i=0;i<=LEVEL;i++){
printf("%d ",LIST[i]);
}
printf("}\n");
}

void part(int n){
int i, first; /* first は、リストの最後の１個前の数値 */

if(n<1) return ;
// LEVEL++; /* 分割する数が１増えた */
LIST[++LEVEL]=n; /* リストの最後に付け足す */
print(); /* 組み合わせを表示 */
COUNT++; /* 件数をカウント */

first=(LEVEL==0) ? 1 : LIST[LEVEL-1];

for(i=first;i<=n/2;i++){
LIST[LEVEL]=i; /* リストの最後を置き換える */
part(n-i);
}
LEVEL--;
return;
}

void main(void){
int N;

N=5;

LIST=(int *)calloc(N, sizeof(int));
if(LIST==NULL){
fprintf(stderr, "作業メモリが確保できませんでした。\n");
exit(EXIT_FAILURE);
}

part(N);

printf("%d通り\n", COUNT);

free(LIST);

exit(EXIT_SUCCESS);
}

お礼

このように丁寧なプログラムまで書いて頂きありがとうございます!感謝いたします！

回答No.4

kapura

すみません。既に気付かれていると思いますが、訂正も不適切ですね。
「@nを得るには@n-1, @n-2, ..., @n-[n/2]が得られている必要がある」，{[n/2], [n/2] or [n/2]+1}は「@n-[n/2]の中で左端の数が[n/2]以上のリストの左端に[n/2]をつけ加えたもの」ですね。

お礼

良かった、これで納得です！ありがとうございました！

回答No.2

kapura

# 既に以下のようなことはわかっているのかもしれませんが・・

n人の場合の全リストを@nと表して、どのリストも昇順になっているとすると

@1: {1}
@2: {1, 1}, {2}
@3: {1, 1, 1}, {1, 2}, {3}
@4: {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}, {4}
@5: {1, 1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 4}, {2, 3}, {5}
...
@n: {1, ...}, ..., ← @n-1のリストの左端に1をつけ加えたもの
　　{2, ...}, ..., ← @n-2の中で左端の数が2以上のリストの左端に2をつけ加えたもの
　　{3, ...}, ..., ← @n-3の中で左端の数が3以上のリストの左端に3をつけ加えたもの
　　...,
　　{[n/2], [n/2] or [n/2]+1}, ← @[n/2]の中で左端の数が[n/2]以上のリストの左端に[n/2]をつけ加えたもの (nが偶数なら{[n/2], [n/2]}、奇数なら{[n/2], [n/2]+1})
　　{n}

という風に見ることができるのではないでしょうか。この考え方でいけば、@nを得るのに @n-1, @n-2, ..., @[n/2]-1(, @[n/2]) が先に得られている必要があると思います ([]はガウス記号)。

お礼

早速の回答ありがとうございます！とても参考になりそうです。

回答No.1

ngsvx

思いつきです。

10の組み合わせを考えると、

10
10, 9
.
.
.
6, 4
6, 3, 2, 1
.
.
.
1,1,1,1,1,1,1,1,1,1

ですよね？

つまり、最初の数はnを1まで減算していき、
それぞれに、（n-1）のパターンを加えればいいかと。

n=10のとき、減算して6まできたとすると、
6,　....
ですが、...の部分は10-6=4で4の組み合わせのパターンがくればいい気がします。

4のパターンは、
4
3,1,1
2,2
1,1,1,1
ですから、これに6を付け加えて、

6,4
6,3,1,1
6,2,2
6,1,1,1,1

となります。

同じように次は先頭が5になり、10-5=5のパターンを加えていきます。

こんな感じでどうでしょうか？

お礼

なるほど、早速の回答ありがとうございます！参考になります。