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

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

ただいまの
回答率

90.48%

  • PHP

    20912questions

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

  • Java

    14153questions

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

  • C

    3838questions

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

  • アルゴリズム

    422questions

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

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

解決済

回答 9

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 6,528

uer03108

score 93

下記のグループ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("----------------------------------");
        }

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 9

+6

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/08 14:14

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

    キャンセル

checkベストアンサー

+3

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

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

呼び出し側は

char[][] arr = new char[][]{
    {'a','b','c'},
    {'a','b','c'},
    {'a','b','c'}
};
doRecursive(0, arr, "");

こんな感じ。

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/08 14:39

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

    キャンセル

  • 2016/04/09 04:55

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

    キャンセル

  • 2016/04/09 05:12 編集

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

    キャンセル

+2

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

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

p ['A', 'B', 'C'].product([], [1, 2]) 
# [] 

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

<?php

function direct_product(array ...$arrays) {
    if (!$tops = array_shift($arrays)) {
        return [];
    }
    if (!$arrays) {
        foreach ($tops as $top) {
            $r[] = [$top];
        }
        return $r;
    }
    if (!$nexts = direct_product(...$arrays)) {
        return [];
    }
    foreach ($tops as $top) {
        foreach ($nexts as $next) {
            $r[] = array_merge([$top], $next);
        }
    }
    return $r;
}

var_export(direct_product(['A', 'B', 'C'], ['a'], [1, 2]));
/*
array (
  0 => 
  array (
    0 => 'A',
    1 => 'a',
    2 => 1,
  ),
  1 => 
  array (
    0 => 'A',
    1 => 'a',
    2 => 2,
  ),
  2 => 
  array (
    0 => 'B',
    1 => 'a',
    2 => 1,
  ),
  3 => 
  array (
    0 => 'B',
    1 => 'a',
    2 => 2,
  ),
  4 => 
  array (
    0 => 'C',
    1 => 'a',
    2 => 1,
  ),
  5 => 
  array (
    0 => 'C',
    1 => 'a',
    2 => 2,
  ),
)
*/

var_export(direct_product(['A', 'B', 'C'], [], [1, 2]));
/*
array (
)
*/

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/08 23:09

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

    キャンセル

+2

こんにちは。

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

#include <stdio.h>
#include <memory.h>

typedef struct
{
    int start;
    int end;
} Range;

void enumeration(int n, Range* ranges)
{
    int* numbers=(int*)malloc(n*sizeof(int));
    if (numbers == NULL)
return;

    for (int i=0; i < n; ++i) numbers[i]=ranges[i].start;

    _Bool   cont=1;
    while(cont)
    {
        for (int i=0; i < n; ++i)
        {
            printf("%d ", numbers[i]);
        }
        printf("\n");

        for (int i=n-1; 0 <= i; --i)
        {
            if (numbers[i] < ranges[i].end)
            {
                numbers[i]++;
        break;
            }
            else
            {
                numbers[i]=ranges[i].start;
                if (i == 0) cont=0;
            }
        }
    }

    free(numbers);
}

int main()
{
    Range ranges[]=
    {
        {1, 3},
        {1, 5},
        {3, 8}
    };
    int n=sizeof(ranges)/sizeof(ranges[0]);

    enumeration(n, ranges);

    return 0;
}

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/08 23:31

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

    キャンセル

0

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/08 12:34

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

    キャンセル

  • 2016/04/08 14:14

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

    キャンセル

0

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/08 14:14

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/08 14:19

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

    キャンセル

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/09 16:34

    やっと理解できました。。。

    i番目の数 = 全要素数/Σ(これまでの要素) % 考慮している要素

    ですね(多分)。好みで、

    i番目の数 = 全要素数 % {考慮している要素*Σ(これまでの要素) }

    でも行けそうですかね。

    キャンセル

  • 2016/04/10 01:10

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

    キャンセル

0

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

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

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

import java.util.Arrays;
import java.util.function.BinaryOperator;
import java.util.function.Supplier;
import java.util.stream.Stream;

public class Main01 {
    private static <T> Stream<T> cartesian(BinaryOperator<T> aggregator, Supplier<Stream<T>>... streams) {
        return Arrays.stream(streams)
                .reduce((s1, s2) -> () -> s1.get().flatMap(t1 -> s2.get().map(t2 -> aggregator.apply(t1, t2))))
                .orElse(Stream::empty).get();
    }

    public static void main(String[] args) {
        Stream<String> result = cartesian((a, b) -> a + "," + b,
                () -> Stream.of("1", "2", "3"),
                () -> Stream.of("+", "-"),
                () -> Stream.of("8", "9")
         );
        result.forEach(System.out::println);

        cartesian((a, b) -> a + b,
            () -> Stream.of("1", "2", "3"),
            () -> Stream.of("A", "B")
        ).forEach(System.out::println);
    }
}


実行例

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 18:29

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

    キャンセル

関連した質問

同じタグがついた質問を見る

  • PHP

    20912questions

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

  • Java

    14153questions

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

  • C

    3838questions

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

  • アルゴリズム

    422questions

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