順列をC言語で表現

締切済

質問者：tttt12345jp
質問日時：2005/11/15 16:31
回答数：4件

ｍPｎを求めるプログラムをC言語で表現したいです。

例えば、（１、２、３）とあったら
（１
（２
（３
（１、２
（２、１
（２、３
（３、２
（１、３
（３、１
（１、２、３
（１，３，２
（２、１，３
（２，３，１
（３、１、２
（３，２，１

というように表示するプログラムです。どなたか分かる方がいらっしゃいましたら、よろしくお願いいたします。

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (4件)

最新から表示
回答順に表示

No.4

回答者： BLUEPIXY
回答日時：2005/11/16 03:35

#3>これはリストを使っているのでしょうか？

もちろんリスト構造みたいなのを作っても良いのですが、＃３は、単なる文字列の配列です。
扱う構造は、
{"A","B","C",NULL}みたいな最後にNULLがある文字列の配列です。
例えば、３つのリストから２つを選ぶ順列の場合
Permutation(list,2,selected);
１段階目の呼出は、
{"1","2","3",NULL}が与えられたリストで、
2が選ぶべき要素の数、
selectedは{NULL}で中身がない状態のリスト
を受け取ります。
ここでやることは、
{"1","2","3",NULL}から１つを選び、選んだ１つを除いたリストを更に下請けに回すことです。
１を選んだ場合
Permutation({"1","2","3",NULL},2,{NULL});
から
Permutation(残りのリスト,残りの選ぶ数,既に選んだ数のリスト);
Permutation({"2","3",NULL},1,{"1",NULL});
として下請けを呼び出します。
下請けでは、選ぶ数が１つになっていたら、
既に選ばれたリストを表示し、今選ぶ１つを表示してreturnします。
まあ、そんな感じです。
*
やり方はいろいろあるかと思うので、１つの方法に固執しない方がいいと思います。

- 1
- 件

通報する

No.3

回答者： BLUEPIXY
回答日時：2005/11/15 21:57

試しに作ってみました

//-------------------------------------------------------------
/* 指定したリストの順列を表示する */
#include <stdio.h>
#include <malloc.h>

void Permutation(char **list, int select, char **selected){
char **newList, **newSelected, **p;
int listSize, selectSize, i;

//それぞれのリストのサイズを求める
for(listSize=0;list[listSize]!=NULL;listSize++);
for(selectSize=0;selected[selectSize]!=NULL;selectSize++);

if(select==1){//選択するものが１つ
for(i=0;i<listSize;i++){
for(p=selected;*p!=NULL;p++){
printf("%s ", *p);//既に選択されたものを表示
}
printf("%s\n",list[i]);//今選ばれた１つをその後に表示
}
return;
}
newList=(char**)malloc(sizeof(char*)*listSize);//新しいリストサイズが１減る
newSelected=(char**)malloc(sizeof(char*)*selectSize+2);//新しいリストは＋１

for(i=0,p=selected;*p!=NULL;p++){
newSelected[i]=*p;//既に選ばれたリストのコピーを作る
}

for(i=0;i<listSize;i++){
int j;
newSelected[selectSize]=list[i];//新しく選ばれたものをリストに追加
newSelected[selectSize+1]=NULL;
for(j=0,p=newList;j<listSize;j++){
if(j!=i){
*p++=list[j];//選ばれた物を除いたリストのコピー
}
}
*p=NULL;

Permutation(newList, select-1, newSelected);
}

free(newSelected);
free(newList);
}

void main(void){
char *list[]={"1","2","3",NULL};
char *selected[]={ NULL };

Permutation(list,1,selected);//リストから１コ選ぶ順列
Permutation(list,2,selected);//リストから２コ選ぶ順列
Permutation(list,3,selected);//リストから３コ選ぶ順列
}