足し算の項の入れ替え

[sow]

今、a+b+cから
a+b+c
a+c+b
b+a+c
b+c+a
c+a+b
c+b+a
と全ての項を入れ替えたパターンを生成するプログラムを考えているのですが、全く考えつかず困っています。
こういう方法だったらできるかもしれないといった、確信がないアドバイスでも頂ければ嬉しいです。

[みけCAT]

パターンを生成する部分は、C++のstd::next_permutationを使うと簡単でしょう。

コード:

#include <iostream>
#include <algorithm>

int main(void) {
	const int num = 3;
	int order[] = {0, 1, 2};
	char data[] = "abc";
	do {
		std::cout << data[order[0]];
		for (int i = 1; i < num; i++) {
			std::cout << '+' << data[order[i]];
		}
		std::cout << '\n';
	} while (std::next_permutation(order, order + 3));
	return 0;
}

[みけCAT]

入力を受け取る部分も作ってみました。

コード:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>

int main(void) {
	std::vector<int> order;
	std::vector<std::string> data;
	std::string input;
	// 入力を読み込む
	if (!std::getline(std::cin, input)) {
		std::cerr << "read error\n";
		return 1;
	}
	// input.c_str()をそのままデータの書換えを行うstrtok()に渡すとまずいので、コピーする
	char* c_input = new char[input.length() + 1];
	strcpy(c_input, input.c_str());
	// 入力を"+"で分割する
	char* one_data = strtok(c_input, "+");
	do {
		order.push_back(order.size());
		data.push_back(one_data);
	} while ((one_data = strtok(NULL, "+")) != NULL);
	delete[] c_input;

	// パターンを生成する
	do {
		for (std::vector<int>::iterator it = order.begin(); it != order.end(); it++) {
			if (it != order.begin()) std::cout << '+';
			std::cout << data[*it];
		}
		std::cout << '\n';
	} while (std::next_permutation(order.begin(), order.end()));
	return 0;
}

入力例1

コード:

a+b+c

出力例1

コード:

a+b+c
a+c+b
b+a+c
b+c+a
c+a+b
c+b+a

入力例2

コード:

send+me+more+money

出力例2

コード:

send+me+more+money
send+me+money+more
send+more+me+money
send+more+money+me
send+money+me+more
send+money+more+me
me+send+more+money
me+send+money+more
me+more+send+money
me+more+money+send
me+money+send+more
me+money+more+send
more+send+me+money
more+send+money+me
more+me+send+money
more+me+money+send
more+money+send+me
more+money+me+send
money+send+me+more
money+send+more+me
money+me+send+more
money+me+more+send
money+more+send+me
money+more+me+send

[あんどーなつ]

文字列を文字列のまま扱ってみました。
ただ、デバッグ用初期化と書いてあるところを '\0' から '@' などに変えるとセグメンテーションフォルトを起こしてしまうのですが、そのデバッグは私のほうではできなかったです。

コード:

#include <stdio.h>
#include <string.h>

#define MAXLEN 32

void imomushi(const char * const res, const char * const rest) {
	int start = 0;
	int end = 0;
	//printf("INFO: res=%s, rest=%s\n", res, rest);
	while (1) {
		if (strlen(rest) == 0) {
			printf("%s\n", res);
			return;
		}
		if (rest[end] == '+' || rest[end] == '\0') {
			char buf[MAXLEN+1];
			for (int i = 0; i < MAXLEN; i++) buf[i] = '\0'; // デバッグ用初期化
			buf[MAXLEN] = '\0';
			int i;
			strcpy(buf, res);
			if (strlen(res) != 0) strcat(buf, "+");
			strncat(buf, rest+start, end - start);
			i = strlen(buf)+1;
			//buf[i] = '\0';
			if (start != 0) {
				strncpy(buf+i, rest, start - 1);
				if (rest[end] == '+')
					strcat(buf+i, rest + end);
			} else {
				if (rest[end] == '+')
					strcpy(buf+i, rest + end + 1);
				else
					buf[i] = '\0';
			}
			imomushi(buf, buf+strlen(buf)+1);
			if (rest[end] == '\0') return;
			end++;
			start = end;
		} else {
			end++;
		}
	}
}

int main() {
	imomushi("", "send+me+more+money");
	return 0;
}

[あんどーなつ]

王道パターンは、要素をa+b+c+d+eとしたときに、
①[00000],[00001],[00002],[00003],[00004],[00010],[00011],...を作る
②５個の数字が被らないものだけにする
③0～4をa～eに変換して表示
です。

この問題の厄介なところは要素の数だけループしないといけないところです。解決策としては、
・再帰を使う
・スタックを使う（再帰はスタックに変換できるらしいです）
・大きな数字(32bit, 64bit整数など)を除算(/,%)する
・配列をカウントアップしていくルーチンを作る([00000]->[00001]->...[00004]->[00010]->...みたいな感じ)
といったことが思い当たりました。

[かずま]

質問です。同じ文字があった場合、どうするんでしょうか？
例えば、a+b+b だったら、
a+b+b
b+a+b
b+b+a
の 3通りでしょうか？

[box]

とりあえず同じ名称のことは意識せずにやってみた。
Rubyだと2行でできた。＼(^O^)／

コード:

a = ["a", "b", "c"]
puts a.permutation(a.size).collect { |a| a.join("+") }