C++ 重複を許す順列を全列挙するプログラム

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
まあ

C++ 重複を許す順列を全列挙するプログラム

#1

投稿記事 by まあ » 10年前

ご質問させていただきます。

nケタのm(0,1,2...m-1)からなる重複を許す順列を全列挙(出力)するプログラムをC++で考えています。

たとえばn=3のm=5(0,1,2,3,4)
だった場合
0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 1 0

...

4 3 4
4 4 0
4 4 1
4 4 2
4 4 3
4 4 4

みたいな感じです。 数値と数値の間はタブやスペースで区切られているとうれしいのですが
頭の固くプログラミングの知識も乏しい私では、なかなか思いつかなくて困っております。

ご教授お願いいたしますm(_ _)m

アバター
usao
記事: 1887
登録日時: 11年前

Re: C++ 重複を許す順列を全列挙するプログラム

#2

投稿記事 by usao » 10年前

>思いつかなくて
とは,何が思いつかないのでしょう?

処理手順(アルゴリズム)は,あなたが結果例を示す際に行ったことそのものだと思います.
(あとは表示するだけ……では?)

non
記事: 1097
登録日時: 13年前

Re: C++ 重複を許す順列を全列挙するプログラム

#3

投稿記事 by non » 10年前

>たとえばn=3のm=5(0,1,2,3,4)

nやmを入力する必要がありますか?m<=10ですか?m>10の可能性はありますか?
non

たいちう
記事: 418
登録日時: 13年前

Re: C++ 重複を許す順列を全列挙するプログラム

#4

投稿記事 by たいちう » 10年前

色んな方法があるけど、一番簡単なのはこんな感じでしょうか。

コード:

#include <iostream>

void func(int n, int m) {
	const int maxM = 10;
	int buf[maxM] = { 0 };

	for (;;) {
		for (int i = 0; i < n; i++)
			std::cout << buf[i] << " ";
		std::cout << std::endl;

		int index = n - 1;
		for (;;) {
			if (++buf[index] < m) break;
			buf[index] = 0;
			if (--index < 0) return;
		}
	}
}

int main() {
	func(3, 5);
	return 0;
}

かずま

Re: C++ 重複を許す順列を全列挙するプログラム

#5

投稿記事 by かずま » 10年前

m は 36までということで。

コード:

#include <stdio.h>
#include <math.h>

int n = 3, m = 5;

void print(int i, int k)
{
    if (k == 0) return;
    print(i/m, k-1);
    putchar("0123456789abcdefghijklmnopqrstuvwxyz"[i%m]);
}

int main(void)
{
    int i, k = (int)pow(m, n);
    for (i = 0; i < k; i++) print(i, n), putchar('\n');
    return 0;
}
C++ ではなく、C で書いてしまったので、
C++ は自分で考えてください。

かずま

Re: C++ 重複を許す順列を全列挙するプログラム

#6

投稿記事 by かずま » 10年前

スペースを出すのを忘れていました。
また、n = 8, m = 16 や、n = 32, m = 2 のとき無限ループにならないようにしました。

コード:

#include <stdio.h>
#include <math.h>
 
unsigned n = 3, m = 5;
 
void print(unsigned i, unsigned k)
{
    if (k == 0) return;
    print(i/m, k-1);
    putchar("0123456789abcdefghijklmnopqrstuvwxyz"[i%m]);
    putchar(' ');
}
 
unsigned main(void)
{
    unsigned i = 0, k = (unsigned)(pow(m, n) - 1);
    do {
        print(i, n);
        putchar('\n');
    } while (i++ != k);
    return 0;
}

まあ

Re: C++ 重複を許す順列を全列挙するプログラム

#7

投稿記事 by まあ » 10年前

>>usaoさん
その結果例を示す際に行った処理を言語としてかけないことにたいして 思いつかないと表現しました。
失礼いたしました。。。

>>nonさん
m<=10で大丈夫です。 m>10の可能性はほぼありません。


>>たいちうさん
こういった組み方があるんですね。 
まだプログラミングに慣れてない身としての感想ですが、非常に理解しやすく、感動しました。
これを参考に書き方を少しアレンジしていきたいと思います。


>>かずまさん
提供ありがとうございます。
C言語を勉強したことがないので、C++と似通ったところはわかるのですが、いまだ理解に時間がかかっています。
しかしとても参考になると思うので、C言語を勉強しつつ理解に至るまで参考にさせていただきます。



皆様、ありがとうございました。

閉鎖

“C言語何でも質問掲示板” へ戻る