Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
8
Help us understand the problem. What is going on with this article?
@saka1029

Java8のStreamで順列を生成

More than 3 years have passed since last update.

与えられたリストからn個の要素を取り出す順列をストリームとして生成します。

    static <T> List<T> cons(T head, List<T> tail) {
        List<T> list = new ArrayList<>();
        list.add(head);
        list.addAll(tail);
        return list;
    }

    static <T> List<T> remove(T e, List<T> list) {
        List<T> newList = new ArrayList<>(list);
        newList.remove(e);
        return newList;
    }

    public static <E> Stream<List<E>> permutations(int n, List<E> list) {
        if (n <= 0) return Stream.of(new ArrayList<>());
        return list.stream()
            .flatMap(h -> permutations(n - 1, remove(h, list))
                .map(t -> cons(h, t)));
    }

リストの中から要素をひとつ取り出します(h)。残りの要素(remove(h, list))の順列をすべて求めて、得られたそれぞれのリストの先頭に取り出した要素(h)を追加(cons(h, t))します。これで取り出した要素を先頭とするすべての順列が求まります。すべての要素についてこれを行うとすべての順列が得られます。

cons()はLisp系の言語や関数型言語をやっている人から見ると笑いものですね。

リスト[1, 2, 3]の中から2つ取る順列を生成してみます。

    @Test
    public void testPermutationsN() {
        permutations(2, Arrays.asList(1, 2, 3))
            .forEach(System.out::println);
    }

結果は以下のようになります。

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

これを使って覆面算「SEND + MORE = MONEY」を解いてみます。
問題に表れる英字はS, E, N, D, M, O, R, Yの8種類なので、リスト[0, 1, ... , 9]から8個を取り出す順列を得て、フィルターで式を満たすかどうかをチェックします。SとMは先頭に現れるので0にはなりません。

    int number(int... args) {
        return IntStream.of(args).reduce(0, (a, b) -> 10 * a + b);
    }

    boolean check(int s, int e, int n, int d, int m, int o, int r, int y) {
        if (s == 0 || m == 0) return false;
        int send = number(s, e, n, d);
        int more = number(m, o, r, e);
        int money = number(m, o, n, e, y);
        if (send + more != money) return false;
        System.out.printf("%s + %s = %s%n", send, more, money);
        return true;
    }

    @Test
    public void testSendMoreMoney() {
        permutations(8, Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9))
            .filter(l -> check(
                l.get(0), l.get(1), l.get(2), l.get(3),
                l.get(4), l.get(5), l.get(6), l.get(7)))
            .forEach(System.out::println);
    }

結果は以下のようになります。

9567 + 1085 = 10652
[9, 5, 6, 7, 1, 0, 8, 2]

私の環境ではpermutations(8, Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9))の後に.parallel()をつけると少しだけ速くなりました。

リストのストリームではなくリストのリストを返す場合は以下のようになります。

    public static <E> List<List<E>> permutationsList(int n, List<E> list) {
        if (n <= 0) return Arrays.asList(Arrays.asList());
        List<List<E>> result = new ArrayList<>();
        for (E head : list)
            for (List<E> tail : permutationsList(n - 1, remove(head, list)))
                result.add(cons(head, tail));
        return result;
    }

こっちの方が分かりやすいように思えるのは古い人間だからなのでしょうか?

8
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
8
Help us understand the problem. What is going on with this article?