組み合わせ列挙の実装

Question

前提・実現したいこと

Javaで再帰を使用して、{0,1}のビット列を組み合わせ列挙するシンプルな実装がちょっとわからず、教えていただきたいです。

nを要素数とします。例えばn=3とすると、
アウトプットとして、以下のビット列を列挙した 2^3(=8) 個のStringの配列(ないしはリスト)を取得したいです。
{111,110,101,100,011,010,001,000}

任意のnに対して、上記の結果が得られる実装を考えていたのですが、
以下のような再帰でない、かつ、冗長な実装しか思いつかず、、、

import java.util.ArrayList;
import java.util.List;

public class Sample {

	public static void main(String[] args) {

		int n = 3;
		int num_to = (int)Math.pow(2, n)-1;
		List<String> result = new ArrayList<>();
		for (int i = num_to; i >= 0; i--) {
			String bin = String.format("%"+n+"s",Integer.toBinaryString(i))
					.replace(' ', '0');
			result.add(bin);
		}

		for (String str : result) {
			System.out.println(str);
		}

	}
}

よろしくお願いします。

Comments

[swordone]

「再帰を使用して」とあるのに対し、このコードでは再帰を使用していないのですがそれはいいのでしょうか？

[d_tutuz]

失礼しました。冗長な実装として挙げた例がよくありませんでした。再帰の学習をしていたので、再帰で解けると嬉しいです。

Answer 1

質問文にある方法を for でなく、Stream を使うようにしたもの、
再帰を使うようにしたものの両方を書いてみました。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;;

public class SampleZ {
    public static void main(String[] args) {
        for (int i = 0; i < 4; i++) {
            System.out.println(conbinationA(i));
            System.out.println(conbinationB(i));
        }
    }

    public static List<String> conbinationA(int keta) {
        List<String> list = new ArrayList<String>();
        if (keta > 0) {
            int max = (int) Math.pow(2, keta);
            IntStream.range(0, max).boxed().collect(Collectors.toList()).forEach(
                    i -> list.add(String.format("%" + keta + "s", Integer.toBinaryString(i)).replaceAll(" ", "0")));
        }
        return list;
    }

    public static List<String> conbinationB(int keta) {
        List<String> list;
        switch (keta) {
        case 0:
            list = new ArrayList<String>();
            break;
        case 1:
            list = new ArrayList<>(Arrays.asList("0", "1"));
            break;
        default:
            list = conbinationB(keta - 1); // 再帰
            List<String> list1 = new ArrayList<String>(list);
            list.replaceAll(str -> "0" + str);
            list1.replaceAll(str -> "1" + str);
            list.addAll(list1);
            break;
        }
        return list;
    }
}

実行結果

Answer 2

別に冗長でもないと思います。しいて言うなら

• (int)Math.pow(2,n)よりは1 << nのようにビット演算
• replaceは1回だけのはずなのでreplaceAllを使う

くらいでしょうか。
おそらく冗長と感じている原因はformat周りだと思いますが、10進や16進のようにゼロ埋めで変換する方法が2進には用意されていないよう(調べて知った)なので仕方がないかと。
これを解消しようとするなら、

"00"のような(桁数-1)文字分の0を用意しておいて、2進変換した数をつなげてsubstring

のようになりますが、まず前半で余計にループなどを使用することになり、逆に冗長になるうえ、String生成回数も大幅に増えてしまいます。

また「再帰を使用して」を守るなら、

public class Sample {

    public static void main(String[] args) {

        int n = 3;
        List<String> list = conbination(Arrays.asList(""), n);

        for (String str : result) {
            System.out.println(str);
        }

    }

    public static List<String> conbination(List<String> binary, int count) {
        if (count <= 0) return binary;
        List<String> list = new ArrayList(binary.size() * 2);
        for (String s : binary) {
            list.add(s + 0);
            list.add(s + 1);
        }
        return conbination(list, count - 1);
    }
}

こんなことになると思いますが、やっぱりString生成回数が多くなります。

Comments

[d_tutuz]

swordoneさん
再帰の実装例、ありがとうございます！
Listを使用することでうまく実装できるのですね。勉強になります！

>(int)Math.pow(2,n)よりは1 << nのようにビット演算
>replaceは1回だけのはずなのでreplaceAllを使う
こちらについてもコメントありがとうございます！