プログラマ専用SNS ミクプラ

初めて質問するので勝手がわからないのですがどうぞよろしくお願いいたします。

http://yoshiiz.blog129.fc2.com/blog-entry-120.html
↑このＵＲＬを参考に組み合わせ問題を解こうとしています。
ソースはこれです↓

#include <stdio.h>

int next_perm(int *p, int n)
{
int i, j, k, tmp;
for(i = n - 1; i > 0 && p[i-1] >= p; i--);
if(i == 0) return 0;
for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
tmp = p[i-1], p[i-1] = p[j], p[j] = tmp;
for(k = 0; k <= ((n-1)-i)/2; k++){
tmp = p[i+k], p[i+k] = p[(n-1)-k], p[(n-1)-k] = tmp;
}
return 1;
}

int main(void)
{
char s[5] = {'a', 'b', 'c', 'd', 'e'};
int p[5] = {0, 0, 0, 1, 1};
int i;
do {
for(i = 0; i < 5; i++)
if(p == 0) printf("%c", s);
printf("\n");
} while(next_perm(p, 5));

return 0;
}

abcdeの５組の中から３組をこのように↓選んで表示することは自分で確認しました。
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde

そこで質問なのですが、仮にa市、b市、c市、d市、e市の人口を{100,200,300,400,500}のように設定した場合、
以下のように表現したいです。どのようなプログラムを作成すればいいでしょうか。
abc={100,200,300}=600
abd={100,200,400}=700
abe={100,200,500}=800
acd={100,300,400}=800
ace={100,300,500}=900
ade={100,400,500}=1000
bcd={200,300,400}=900
bce={200,300,500}=1000
bde={200,400,500}=1100
cde={300,400,500}=1200

comma をつけるのが面倒なのでサボっていますが、こんなもんでどうでしょうか？

コード:

#include <stdio.h>

int next_perm(int *p, int n)
{
    int i = n, j, tmp;
    while (--i > 0 && p[i-1] >= p[i]) ;
    if (i == 0) return 0;
    for (j = n; --j > i && p[i-1] >= p[j]; );
    tmp = p[i-1], p[i-1] = p[j], p[j] = tmp;
    for (; i < --n; i++) tmp = p[i], p[i] = p[n], p[n] = tmp;
    return 1;
}

int main(void)
{
    char s[5] = {　'a', 'b', 'c', 'd', 'e'　};
    int p[5] = {　0, 0, 0, 1, 1　};
    int m[5] = { 100, 200, 300, 400, 500 };
    int i, sum;
    do {
        for (i = 0; i < 5; i++)
            if (p[i] == 0) printf("%c", s[i]);
        printf(" = {");
        for (sum = i = 0; i < 5; i++)
            if (p[i] == 0) printf(" %d", m[i]), sum += m[i];
        printf(" } = %d\n", sum);
    } while (next_perm(p, 5));
    return 0;
}

ありがとうございました！！動作を確認することができました！！

続けて質問して大変恐縮なのですか、
a={0,1,1,1,0}
b={1,0,0,1,1}
c={1,0,0,1,1}
d={1,1,1,0,0}
e={0,1,1,0,0}
というデータがあったとします。
ここでは、0は隣接（または同じ）していることを表しています。
1は離れていることを表します。
つまり市aは市aと市eと隣接しています（同じ場合は隣接している0とみなします）。

http://yoshiiz.blog129.fc2.com/blog-entry-120.html
↑このＵＲＬを参考に５都市の中から３都市を選ぶことができたとして、
この場合以下のように表示するにはどうすればよろしいのでしょうか。よろしくお願いいたします。
abc:not rinsetu
abd:not rinsetu
abe:not rinsetu
acd:not rinsetu
ace:not rinsetu
ade:rinsetu
bcd:not rinsetu
bce:not rinsetu
bde:not rinsetu
cde:not rinsetu

adeにおいて市aと市dは隣接していませんが、市eを介して隣接しているため「rinsetu」と判断します。

出来れば、a市、b市、c市、d市、e市の人口を{100,200,300,400,500}と設定している場合、rinsetuと判断されたadeのみを
ade={100,400,500}=1000
と表示させたいです。
出来れば、a市、b市、c市、d市、e市の人口を{100,200,300,400,500}と設定している場合、rinsetuと判断されたadeのみを
ade={100,400,500}=1000
と表示させたいです。

a, b, c の都市の場合、a-b間、b-c間、c-a間の 3個のうち、
2個以上が切れていたらダメ、
切れているのが 0個か 1個なら接続されていることになるでしょう。

コード:

#include <stdio.h>

int next_perm(int *p, int n)
{
    int i, j, tmp;
    for (i = n; --i > 0 && p[i-1] >= p[i]; ) ;
    if (i == 0) return 0;
    for (j = n; --j > i && p[i-1] >= p[j]; );
    tmp = p[i-1], p[i-1] = p[j], p[j] = tmp;
    for (; i < --n; i++) tmp = p[i], p[i] = p[n], p[n] = tmp;
    return 1;
}

int t[5][5] = {
   { 0, 1, 1, 1, 0 },
   { 1, 0, 0, 1, 1 },
   { 1, 0, 0, 1, 1 },
   { 1, 1, 1, 0, 0 },
   { 0, 1, 1, 0, 0 },
};

int connected(int *p)
{
    int q[3], i, j;
    for (j = i = 0; i < 5; i++)
        if (p[i] == 0) q[j++] = i;
    return t[q[0]][q[1]] + t[q[1]][q[2]] + t[q[2]][q[0]] <= 1;
}

int main(void)
{
    char s[5] = { 'a', 'b', 'c', 'd', 'e' };
    int p[5] = { 0, 0, 0, 1, 1 };
    int m[5] = { 100, 200, 300, 400, 500 };
    int i, sum;
    do {
        if (connected(p)) {
            for (i = 0; i < 5; i++)
                if (p[i] == 0) putchar(s[i]);
            printf(" = {");
            for (sum = i = 0; i < 5; i++)
                if (p[i] == 0) printf(" %d", m[i]), sum += m[i];
            printf(" } = %d\n", sum);
        }
    } while (next_perm(p, 5));
    return 0;
}

迅速かつ分かりやすいプログラムを提示頂きありがとうございます！！

また質問なのですが、
仮に下限値１が６００、上限値２が１２００だと与えられてるとして、先ほどの隣接の条件を満足している「rinsetu」と印刷された合計値が６００よりも大きく１２００よりも小さければ「OK」と表示される、（６００＜＝rinsetuの合計＜＝１２００）
６００よりも小さいまたは１２００よりも大きい合計値の場合は「ＮＯ」と表示するようなプログラムはどうすればよろしいのでしょうか。

ade={100,400,500}=1000：ＯＫ
という具合です。

できればもしこのrinsetuの合計値がＯＫと複数表示された場合、最大値を求めるにはどうすればよいのでしょうか。

プログラマ専用SNS ミクプラ

組み合わせ問題について

組み合わせ問題について

Re: 組み合わせ問題について

お礼と組み合わせ問題について（２）

Re: 組み合わせ問題について

お礼と組み合わせ問題について３