再帰を使わずに再帰のようなことを実現したい

Question

[1,1,1,1,1]
[1,1,1,1,2]
...
[1,1,1,1,9]
[1,1,1,2,2]
[1,1,1,2,3]
...
[8,9,9,9,9]
[9,9,9,9,9]

上記のような出力をするC++のプログラムを、再帰を使わずに実現したいです。
どうすればよいでしょうか。

以下は、再帰を使った実装です（一応、丸投げではないアピールです）。

#include <iostream>
#include <vector>

using namespace std;

void recurse(vector<int> *v, int len, int max)
{
	int start;
	int i, j;
	if (v->size() == len) {
		cout << "[";
		for (j = 0; j < len-1; j++) {
			cout << v->at(j) << ",";
		}
		cout << v->at(len-1) << "]" << endl;
		return;
	}
	if (v->size() == 0) {
		start = 1;
	} else {
		start = v->back();
	}
	for (i = start; i <= max; i++) {
		v->push_back(i);
		recurse(v, len, max);
		v->pop_back();
	}
}

int main(void)
{
	vector<int> v;
	recurse(&v, 5, 9);
	return 0;
}

【追記】
長さと最大値は可変にしたいです。最小値は、とりあえずは1で固定です。

【更に追記】
baseballyamaさんの回答を元に書いた、再帰無しのコードです。一応再帰無しで同等の処理が実現できましたので解決済みとします。回答してくださった皆様、ありがとうございました！ただ、僕としては、maxが2桁以上の場合でも正常に動作してほしいですし、再帰処理を再帰無しで記述する「普遍的な」方法を知りたかったです。その方法を知れれば、機械的に再帰無しコードに書き換えられるような…そんなメソッドが知りたかったのです。

#include <iostream>

using namespace std;

void recurse(int len, int max)
{
	// 数値型↔文字型の変換は、0x30を加算・減算することで行う
	string smax = string(5, max + 0x30);
	int imax = stoi(smax);

	for (int i = 1; i <= imax; i++) {
		bool flag = true;
		string s = to_string(i);

		for (int j = 0; j < s.size(); j++) {
			// 要素が1以上max以下の条件を満たさない場合は出力しない
			if (s[j] - 0x30 < 1 || s[j] - 0x30 > max) {
				flag = false;
				break;
			}
			// 左から右に昇順でない場合は出力しない
			if (j > 0 && s[j - 1] > s[j]) {
				flag = false;
				break;
			}
		}

		if (flag) {
			cout << "[";
			for (int j = 0; j < s.size(); j++) {
				cout << s[j];
				if (j < s.size() - 1) {
					cout << ",";
				}
			}
			cout << "]" << endl;
		}
	}
}

int main(void)
{
	recurse(5, 9);
	return 0;
}

Comments

[iwanote]

これは桁数があらかじめ決まっているものですか？決まっているならfor文で回せばいいですし、決まっていないならプログラム中のprintfのところがおかしいように思われます

[toshiyan]

ご指摘ありがとうございます。ご指摘の内容をソースコードに反映しました。配列の長さと最大値は、引数として渡すことを想定しています。

Answer 1

カウンタ変数を1から100,000までカウントアップしていき、各桁を拾えば良いと思います（0である桁があるケースは除外が必要）。各桁を拾うのは10で割った剰余を順に使えば良いです。

Comments

[toshiyan]

回答ありがとうございます。

[退会済みユーザー]

9で割ったあまりに1足すとか。

Answer 2

正月の遊びのつもりで作ってみましたが、出力仕様に合っていますか。

#include <iostream>
#include <vector>

using namespace std;

void init(vector<int> *v, int len) {
    for (int i = 0; i < len; i++) v->push_back(1);
}

void print(vector<int> *v) {
    cout << "[";
    for (int i = 0; i < v->size()-1; i++) cout << v->at(i) << ",";
    cout << v->at(v->size()-1) << "]" << endl;
}

bool checkMax(vector<int> *v, int start, int end, int max) {
    for (int i = start; i <= end; i++) {
    	if (v->at(i) < max) return false;
    }
    return true;
}

int main(void)
{
    vector<int> v;
    int len = 5;
    int max = 9;

    init(&v, len);

    while (true) {
    	print(&v);

    	if (checkMax(&v, 0, len-1, max)) break;

        for (int i = len-1; i >= 0; i--) {
        	if (v.at(i) < max) {
        		if (i < len-1) {
        			if (checkMax(&v, i+1, len-1, max)) {
        				v.at(i)++;
        			}
        		} else {
        			v.at(i)++;
        		}
        		break;
        	} else if (v.at(i) == max) {
        		if (i > 0) {
        			if (v.at(i-1) < max) {
        				v.at(i-1)++;
        				if (checkMax(&v, i, len-1, max)) {
        					for (int j = i; j < len; j++) v.at(j) = v.at(i-1);
        				}
        				break;
        			}
        		}
        	}
        }
    }
    return 0;
}

Comments

[toshiyan]

私の要件をすべて満たしてくれていますね。ベストアンサーを、こちらの正しいコードに変えさせていただきます。回答ありがとうございました！

Answer 3

C++など不要。そう、シェル芸ならね！

$ echo [{1..9},{1..9},{1..9},{1..9}]|tr ' ' '\n'

Comments

[toshiyan]

回答ありがとうございます。参考になります。

[mkgrei]

https://stackoverflow.com/questions/478898/how-to-execute-a-command-and-get-output-of-command-within-c-using-posix
C++でコマンドを生成してからそのままシェル芸を投げればいいのですね！

Answer 4

ご質問の内容を正確に把握せずに回答してしまいました。大変申し訳ございません。
再帰処理を使用しないとすると以下のような処理が妥当なのではないかと思いました。
※但し私C++は書いたことがないので、javaをイメージして記載してしまいました。
※なので、不適当なプログラムを記載している部分があるかもしれません。
※コメントを受けて修正しました。

#include <iostream>
#include <stdexcept>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

// char文字を int型 に変換(数字以外が来た場合は -1 を返却)
int ctoi(char c) {
	switch (c) {
	case '0':
		return 0;
	case '1':
		return 1;
	case '2':
		return 2;
	case '3':
		return 3;
	case '4':
		return 4;
	case '5':
		return 5;
	case '6':
		return 6;
	case '7':
		return 7;
	case '8':
		return 8;
	case '9':
		return 9;
	default:
		return -1;
	}
}

// len 文字数の数字を カンマ区切りで出力
// 但し max 以上の数字が入っている場合は出力を実施しない
// 出力例: [2,2,2,2,2]
void printNums(int len, int max) {

	// 出力最大値を取得
	string maxValue = "";
	for (int i = 0; i < len; i++) {
		maxValue = maxValue + std::to_string(max);
	}
	int maxvalue = std::stoi(maxValue);

	// 0 から 出力最大値まで走査
	for (int i = 1; i <= maxvalue; i++) {

		// 出力対象フラグ初期化
		bool printFlag = true;

		// 出力対象の数字を文字列に変換
		std::ostringstream sout;
		sout << std::setfill('0') << std::setw(5) << i;
		std::string str = sout.str();

		// 出力対象に max 以上の数値が含まれている場合は出力処理を実施しない
		for (int j = 0; j < (int) str.size(); j++) {
			if (ctoi(str[j]) > max || ctoi(str[j]) == 0) {
				printFlag = false;
				break;
			}
		}

		// 出力対象の場合は出力を実施
		if (printFlag) {
			cout << "[";
			int length = str.length();
			for (int j = 0; j < length; j++) {
				cout << str[j];
				if (length != (j + 1)) {
					cout << ", ";
				}
			}
			cout << "]" << endl;
		}

	}

}

// メイン処理
int main() {

	// 5桁で全ての数字が2以下のものを出力
	printNums(5, 2);

	// 結果返却
	return 0;

}

※以下当初の回答
/*******************************************************************/

単純に for文 を4重に回すのではダメなのですか?

#include <iostream>
using namespace std;

int main() {

	// 1桁目を 1 から 9 まで走査
	for (int i = 1; i < 10; i++) {

		// 2桁目を 1 から 9 まで走査
		for (int j = 1; j < 10; j++) {

			// 3桁目を 1 から 9 まで走査
			for (int k = 1; k < 10; k++) {

				// 4桁目を 1 から 9 まで走査
				for (int l = 1; l < 10; l++) {

					// 標準出力 形式:"[i, j, k, l]"
					cout << "[" << i << ", " << j << ", " << k << ", " << l << "]" << endl;

				}

			}

		}

	}

	// 結果返却
	return 0;

}

Comments

[toshiyan]

回答ありがとうございます。要素の数は可変にしたいです…。

[baseballyama]

そしたら、そのi, j, k, l を引数にしたメソッドを作成し、それをmainから呼べばよいのではないでしょうか。

[toshiyan]

すみません。よくわからないので、コードで提示していただけないでしょうか。理解力がなくて申し訳ございません…。

[baseballyama]

当初の回答はご質問を正確に理解していないで記載してしまいました。ご質問を再度読み返したのち、再度プログラムを記載させて頂きました。お役に立てたら幸いです。

[toshiyan]

丁寧な対応ありがとうございます。嬉しいです。
私の方でも実装しましたところ、以下のバグが含まれていました。

・[1,0,0,0,0]のような配列も出力されてしまう。
・[1,1,1,2,1]のような、要素が左から右に昇順になっていないものは、出力したくありません。このプログラムでは出力してしまいます。
・maxが2桁以上の場合に対応していない（これは私の伝え忘れです。すみません…）。

再帰を使って楽に書けるコードを再帰無しで無理に書こうとすると、柔軟性がなくなってしまうものなんですかね…（例えばmaxは一桁の数値にしか対応しない、など）。

一応、私の方で実装したコードを質問内に載せておきます。

[baseballyama]

・[1,0,0,0,0]のような配列も出力されてしまう。
⇒すいません。これは要件を把握できていませんでした。

・[1,1,1,2,1]のような、要素が左から右に昇順になって...
⇒そうなんですね。了解しました。

・maxが2桁以上の場合に対応してい...
⇒そうなんですね。了解しました。

私は再帰処理に抵抗がないので、この場合再帰で書きますが、再帰はわかりづらいという人が一定数いることも事実です。
ただ、このケースの場合、上記要件も取り込んで再帰なしで実装するとなると、冗長になると思います。

まずは、上記要件漏れを修正してソースを更新しておきます。

Answer 5

配列に11...11から99...99までの数字全部入れてその条件に当てはまらないものを消していったらどうでしょうか
配列に収まるかはわかりませんが...

Comments

[toshiyan]

回答ありがとうございます。