質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

PHP

PHPは、Webサイト構築に特化して開発されたプログラミング言語です。大きな特徴のひとつは、HTMLに直接プログラムを埋め込むことができるという点です。PHPを用いることで、HTMLを動的コンテンツとして出力できます。HTMLがそのままブラウザに表示されるのに対し、PHPプログラムはサーバ側で実行された結果がブラウザに表示されるため、PHPスクリプトは「サーバサイドスクリプト」と呼ばれています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

9回答

19625閲覧

for文で全ての組み合わせを考える

uer03108

総合スコア194

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

PHP

PHPは、Webサイト構築に特化して開発されたプログラミング言語です。大きな特徴のひとつは、HTMLに直接プログラムを埋め込むことができるという点です。PHPを用いることで、HTMLを動的コンテンツとして出力できます。HTMLがそのままブラウザに表示されるのに対し、PHPプログラムはサーバ側で実行された結果がブラウザに表示されるため、PHPスクリプトは「サーバサイドスクリプト」と呼ばれています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

2グッド

0クリップ

投稿2016/04/08 03:18

編集2016/04/08 14:08

下記のグループA, B, Cがあるとします。

グループA:①~③
グループB:①~⑤
グループC:③~⑧

すべての組み合わせを考える場合は、

for(int i=1;i<=3;i++){ //グループA
for(int j=1;j<=5;j++){ //グループB
for(int k=3;k<=8;k++){ //グループC
//処理
}}}

として、グループの数だけfor文を作成すれば処理が可能です。

質問ですが、グループの数が分からない場合は、for文をn個作成する必要がありますが、代替の手段はあるでしょうか。

予め最大数のfor文を作っておけば、出来なくはないですが。

多くの回答有難うございました。
取り敢えず、再帰を使わないバージョンでは、下記で動きました。
再帰を使った方がラクですね。

public static void Tree_2(){ int data[][] = { {1,2} ,{3,4,5} ,{6,7,8} ,{9,10,11,12} ,{13,14} ,{15} }; // System.out.println(data.length); List<Integer>[] list = new ArrayList[data[0].length]; List<Integer>[] listPre = new ArrayList[data[0].length]; for(int j=0;j<data[0].length;j++){ listPre[j] = new ArrayList<Integer>(); listPre[j].add(data[0][j]); } list[0] = new ArrayList<Integer>(listPre[0]); for(int i=1;i<data.length;i++){ int num=0; list = new ArrayList[data[i].length*listPre.length]; for(int j=0;j<listPre.length;j++){ for(int k=0;k<data[i].length;k++){ list[num] = new ArrayList<Integer>(listPre[j]); list[num].add(data[i][k]); // System.out.println(num + ":" + list[num]); num++; }} //コピー listPre = new ArrayList[list.length]; for(int j=0;j<list.length;j++){ listPre[j] = new ArrayList<Integer>(list[j]); // System.out.println(j + ":" + list[j]); } // System.out.println("----------------------------------"); } }
KiyoshiMotoki, afroscript👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答9

0

再帰を使う方法になるのではないでしょうか?
グループのリストやグループ○までの組み合わせなどを引数にとって、
再帰的に呼び出して組み合わせを作っていく格好になると思います。

投稿2016/04/08 03:21

swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

uer03108

2016/04/08 05:14

再帰ですか。 有難うございます。
guest

0

ベストアンサー

たとえば「charの2次元配列のすべての組み合わせをカンマで区切って出力する」とかを再帰で書くと、javaの場合こんな感じになりますかね。

java

1static void doRecursive(int i, char[][] arr, String outputString){ 2 if(i == arr.length) { 3 System.out.println(outputString); 4 return; 5 } 6 String delim = (outputString.length()>0) ? "," : ""; 7 for(int j = 0; j < arr[i].length; j++){ 8 doRecursive(i+1, arr, outputString + delim + arr[i][j]); 9 } 10}

呼び出し側は

java

1char[][] arr = new char[][]{ 2 {'a','b','c'}, 3 {'a','b','c'}, 4 {'a','b','c'} 5}; 6doRecursive(0, arr, "");

こんな感じ。

。。。しかし、再帰って地味に呼び出しオーバヘッドがあったりメモリ占有があったりするので実務ではあまり使いたくないなぁ。

投稿2016/04/08 04:38

編集2016/04/08 04:44
tkturbo

総合スコア5572

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

uer03108

2016/04/08 05:39

サンプルまで書いて頂き、有難うございます。 再帰の中でfor文で再起を呼び出していて、理解に時間がかかりました。 treeの様なイメージですかね。 勉強になりました。
tkturbo

2016/04/08 19:55

ちなみに次元数が決まってるなら、その数分ループでネストしたほうが機械にやさしい処理になります。再帰呼び出しを使うとその処理分余計にメモリ領域を圧迫する(処理を行うためのメモリ領域が再帰のたびに新しく確保される)ので、再帰ネストが深くなるほどOutOfMemoryに近づくという罠が。。。
tkturbo

2016/04/08 20:16 編集

ちなみに個人的な「書いてはいけないソース」: static void crashMemory(int mem){ int x = mem + 1; crashMemory(mem); } javaの場合、あっという間にOutOfMemryErrorが発生します。
guest

0

こんにちは。

私も再帰を使った方が良いと思いますが、あえて再帰しない方式にトライです。

C

1#include <stdio.h> 2#include <memory.h> 3 4typedef struct 5{ 6 int start; 7 int end; 8} Range; 9 10void enumeration(int n, Range* ranges) 11{ 12 int* numbers=(int*)malloc(n*sizeof(int)); 13 if (numbers == NULL) 14return; 15 16 for (int i=0; i < n; ++i) numbers[i]=ranges[i].start; 17 18 _Bool cont=1; 19 while(cont) 20 { 21 for (int i=0; i < n; ++i) 22 { 23 printf("%d ", numbers[i]); 24 } 25 printf("\n"); 26 27 for (int i=n-1; 0 <= i; --i) 28 { 29 if (numbers[i] < ranges[i].end) 30 { 31 numbers[i]++; 32 break; 33 } 34 else 35 { 36 numbers[i]=ranges[i].start; 37 if (i == 0) cont=0; 38 } 39 } 40 } 41 42 free(numbers); 43} 44 45int main() 46{ 47 Range ranges[]= 48 { 49 {1, 3}, 50 {1, 5}, 51 {3, 8} 52 }; 53 int n=sizeof(ranges)/sizeof(ranges[0]); 54 55 enumeration(n, ranges); 56 57 return 0; 58}

もしも、組み込み系で使うなら、malloc/freeは禁じ手ですし、そもそも可変長が禁じ手なので、最大のnに対応したメモリを事前に獲得すれば良いです。

う~ん、しかし、我ながらなかなかドン臭いコードです。

投稿2016/04/08 06:45

Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

uer03108

2016/04/08 14:31

回答有難うございました。 シンプルですね。
guest

0

Rubyだと組み込みで専用メソッドが用意されているのが強いです.

Ruby

1p ['A', 'B', 'C'].product(['a'], [1, 2]) 2# [["A", "a", 1], ["A", "a", 2], ["B", "a", 1], ["B", "a", 2], ["C", "a", 1], ["C", "a", 2]] 3 4p ['A', 'B', 'C'].product([], [1, 2]) 5# []

PHPなら自前でゴリゴリですね.

PHP

1<?php 2 3function direct_product(array ...$arrays) { 4 if (!$tops = array_shift($arrays)) { 5 return []; 6 } 7 if (!$arrays) { 8 foreach ($tops as $top) { 9 $r[] = [$top]; 10 } 11 return $r; 12 } 13 if (!$nexts = direct_product(...$arrays)) { 14 return []; 15 } 16 foreach ($tops as $top) { 17 foreach ($nexts as $next) { 18 $r[] = array_merge([$top], $next); 19 } 20 } 21 return $r; 22} 23 24var_export(direct_product(['A', 'B', 'C'], ['a'], [1, 2])); 25/* 26array ( 27 0 => 28 array ( 29 0 => 'A', 30 1 => 'a', 31 2 => 1, 32 ), 33 1 => 34 array ( 35 0 => 'A', 36 1 => 'a', 37 2 => 2, 38 ), 39 2 => 40 array ( 41 0 => 'B', 42 1 => 'a', 43 2 => 1, 44 ), 45 3 => 46 array ( 47 0 => 'B', 48 1 => 'a', 49 2 => 2, 50 ), 51 4 => 52 array ( 53 0 => 'C', 54 1 => 'a', 55 2 => 1, 56 ), 57 5 => 58 array ( 59 0 => 'C', 60 1 => 'a', 61 2 => 2, 62 ), 63) 64*/ 65 66var_export(direct_product(['A', 'B', 'C'], [], [1, 2])); 67/* 68array ( 69) 70*/

投稿2016/04/08 06:10

mpyw

総合スコア5223

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

uer03108

2016/04/08 14:09

回答有難うございます。 Ruby便利ですね。
guest

0

java8 で Strem を使って書いた例です。
参考情報:

  • Cartesian product of streams in Java 8 as stream (using streams only)

http://stackoverflow.com/questions/32631602/

java

1import java.util.Arrays; 2import java.util.function.BinaryOperator; 3import java.util.function.Supplier; 4import java.util.stream.Stream; 5 6public class Main01 { 7 private static <T> Stream<T> cartesian(BinaryOperator<T> aggregator, Supplier<Stream<T>>... streams) { 8 return Arrays.stream(streams) 9 .reduce((s1, s2) -> () -> s1.get().flatMap(t1 -> s2.get().map(t2 -> aggregator.apply(t1, t2)))) 10 .orElse(Stream::empty).get(); 11 } 12 13 public static void main(String[] args) { 14 Stream<String> result = cartesian((a, b) -> a + "," + b, 15 () -> Stream.of("1", "2", "3"), 16 () -> Stream.of("+", "-"), 17 () -> Stream.of("8", "9") 18 ); 19 result.forEach(System.out::println); 20 21 cartesian((a, b) -> a + b, 22 () -> Stream.of("1", "2", "3"), 23 () -> Stream.of("A", "B") 24 ).forEach(System.out::println); 25 } 26}

実行例

1,+,8 1,+,9 1,-,8 1,-,9 2,+,8 2,+,9 2,-,8 2,-,9 3,+,8 3,+,9 3,-,8 3,-,9 1A 1B 2A 2B 3A 3B

投稿2016/04/09 04:52

katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

uer03108

2016/04/09 09:29

難解ですね。。。 数学で言うところの直積に近い考え方でしょうか。
guest

0

ruby ですが、 組み込みの product を使わずにかいてみました。

考え方を記載します。

  1. すべての組み合わせを1列に並べたところを想像します。

最初の組み合わせは すべての配列から 0 番目の要素を選んだものになります。
最後の組み合わせは すべての配列から 最後の要素を選んだものになります。
2 列の長さは すべての配列の要素数を掛け算したものになります。
3 列の i 番目の組み合わせは
最後の配列の ( i % 最後の要素数) 番目の要素
最後から2番目の配列の ( (i / 最後の要素の長さ) % 最後から2番目の要素数) 番目の要素
...
を選んだものとなります。

これをプログラムコードにしてみます。(ここでは ruby で)

1.rb

# 組み合わせを列挙する def products(arys) fail 'Block is not given.' unless block_given? # 組み合わせ数を計算する n = arys.inject(1) { |a, e| a * e.length } (0..n - 1).each do |i| ans = [] j = i arys.reverse_each do |ary| ans.unshift ary[j % ary.length] # ans の先頭に追加 j /= ary.length end yield ans end end arys = [ [1, 2, 3], ['+', '-'], [8, 9] ] products(arys) { |x| p x.join ' '} p ' --------- ruby の Array#product を使う' arys[0].product(*arys.last(arys.length - 1)).each { |x| p x.join ' ' }

実行例

$ 1.rb "1 + 8" "1 + 9" "1 - 8" "1 - 9" "2 + 8" "2 + 9" "2 - 8" "2 - 9" "3 + 8" "3 + 9" "3 - 8" "3 - 9" " --------- ruby の Array#product を使う" "1 + 8" "1 + 9" "1 - 8" "1 - 9" "2 + 8" "2 + 9" "2 - 8" "2 - 9" "3 + 8" "3 + 9" "3 - 8" "3 - 9"

投稿2016/04/08 16:18

katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

uer03108

2016/04/09 07:34

やっと理解できました。。。 i番目の数 = 全要素数/Σ(これまでの要素) % 考慮している要素 ですね(多分)。好みで、 i番目の数 = 全要素数 % {考慮している要素*Σ(これまでの要素) } でも行けそうですかね。
katoy

2016/04/09 16:10

i番目の数 = 全要素数/Σ(これまでの要素) % 考慮している要素 という表現は私にはわかりません。 私は次のように考えています。 10進数表記は各桁に 0...9 を割り当ています。 ここでの方法は、各桁に 対応する配列の要素を割り当ています。
guest

0

私も最近このような処理を実装しましたが、やはり再帰呼び出しで実装しました。
言語はC言語ですが、どの言語でも考え方は一緒ではないでしょうか。
但し、コーディング規約等で再帰呼び出しを禁止しているところもあります(特に組み込み系)。
下手すりゃ無限ループに陥って資源を使い果たすこともあるわけですから、禁止したいのもうなずけます。

投稿2016/04/08 04:35

ttyp03

総合スコア16996

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

uer03108

2016/04/08 05:19

やっぱり、再帰を使用するのがスムーズで自然ですね。 でも、禁止されていると、頭をひねる必要があり厳しそうです。。。 有難うございました。
guest

0

状況が違うかもしれませんが、わたしも最近そういうのやりました。
グループはどんな形式で持っているんでしょうか・・・。状況違うかもしれませんが・・・。

たとえば、各グループが持つ内容が決まっているとすれば、
①〜⑧までの必要な項目を全部持った最終形のarrayを作っておいて、
再帰的に処理するとか。
array_merge_recursiveっていう関数が便利でしたよ。

どんな結果がお望みなのかわかりませんので的外れだったら流してくださいw

投稿2016/04/08 04:27

harumakiyukko

総合スコア20

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

uer03108

2016/04/08 05:14

phpって便利な関数が多いような気がします。 有難うございました。
guest

0

groupのリストを用意して、末尾に決まった値をいれます(例えばNULLとか)。
こうしておくと、forループの継続条件に「決まった値じゃないかぎり」という指定ができます。
なので、可変長に対応できます。

こういう、ループを終わらせるための最後の要素を「番兵」といいます。

投稿2016/04/08 03:22

tnd-.-b

総合スコア247

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

tnd-.-b

2016/04/08 03:34

そういうことじゃないですね。 失礼しました。忘れて下さい。
uer03108

2016/04/08 05:14

「番兵」と言うのですね。 有難うございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問