順列をC言語で表現

質問

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

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

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

回答No.4

BLUEPIXY

#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します。
まあ、そんな感じです。
*
やり方はいろいろあるかと思うので、１つの方法に固執しない方がいいと思います。

回答No.3

BLUEPIXY

試しに作ってみました
//-------------------------------------------------------------
/* 指定したリストの順列を表示する */
#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);//リストから３コ選ぶ順列
}

補足

ありがとうございます。これはリストを使っているのでしょうか？この辺の使い方がよくわからないです。もしよろしければ、少し解説していただけると幸いです。

回答No.2

noname#16765

再帰的に作れると思います。
表示する順番が
（１
（１、２
（１、２、３
（１、３
（１，３，２
（２
（２、１
（２、１，３
（２、３
（２，３，１
（３
（３、１
（３、１、２
（３、２
（３，２，１
みたいなかんじになるとは思いますが・・・

補足

ありがとうございます。再帰をつかえばよいということろまではわかるのですが、そこから先がなんとも。。。ほとんどC初心者といってもいいかもしれません。わかりやすく、解説して頂けたら幸いです。

回答No.1

hello_world

まず貴方はどう考えましたか?
例を書いているのだから解き方(アルゴリズム)は判っているのですよね?
まずそこを書いてどの部分をCでどう表現したらいいのか判らないのか書いてください。

補足

すみませんでした。再帰を使えばよいということろまではわかっています。ですが、何分C言語は初心者で、そこから先が何をしていいのかわからない状況です。最終的には、flexという言語で表現しなければならないのです。まずはC言語でアルゴリズムを理解しようと思い、質問をさせて頂きました。