M.Hiroi's Home Page

続・お気楽 Java プログラミング入門

リストで遊ぼう (2)


Copyright (C) 2017-2021 Makoto Hiroi
All rights reserved.

はじめに

拙作の「immutable な連結リスト」を使った簡単な問題集です。

  1. リストに格納されている数値データの最小値、最大値、合計値、平均値、標準偏差を求めるプログラムを作ってください。
  2. リストを使って「パスカルの三角形」を表示するプログラムを作ってください。
  3. リスト xs において、連続している同じ要素を (code num) に変換するメソッド encode() とそれを元に戻すメソッド decode() を定義してください。code は要素、num は個数を表します。このような変換を「ランレングス符号化」といいます。
  4. 下記に示す経路図において、A から G までの経路をすべて求めるプログラムを作ってください。ただし、経路はリストで表すものとします。 
        Ｂ───Ｄ───Ｆ
  ／│      │
Ａ  │      │
  ＼│      │
    Ｃ───Ｅ───Ｇ

    図 : 経路図
  5. パズル「8 クイーン」を解くプログラムを作ってください。
  6. パズル「農夫と山羊と狼とキャベツの問題」を解くプログラムを作ってください。
    [問題]
    農夫が狼と山羊とキャベツを持って川の左岸にいます。農夫はこれらを川の右岸へ運ばなければいけませんが、ボートにはそのうちのひとつしか乗せることができません。狼は山羊を好んで食べるため、この 2 つを同じ岸に残すことはできません。また、山羊はキャベツを好んで食べるため、この 2 つも同じ岸に残すことはできません。この条件で、荷物をすべて右岸へ運ぶ手順を求めてください。
  7. n 個の整数 1, 2, ..., n の順列を考えます。このとき、i 番目 (先頭要素が 1 番目) の要素が整数 i ではない順列を「完全順列 (derangement)」といいます。1 から n までの整数値で完全順列を生成するプログラムを作ってください。
  8. リストで表した集合 xs を分割するプログラムを作ってください。たとえば、集合 (1 2 3) は次のように分割することができます。 
    1 分割 : ((1 2 3))
2 分割 : ((1 2) (3)), ((1 3) (2)), ((1) (2 3))
3 分割 ; ((1) (2) (3))
  9. k 個の要素をもつ集合 xs を要素数が等しい m 個の部分集合に分割することを考えます。部分集合の要素数 n は k / m になります。分割の仕方をすべて求めるプログラムを作ってください。
  10. 整数 n を 1 以上の自然数の和で表すことを考えます。これを「整数の分割」といいます。整数を分割するとき、同じ自然数を何回使ってもかまいませんが、並べる順序が違うだけのものは同じ分割とします。リストを使って整数 n の分割の仕方をすべて求めるプログラムを作ってください。

●解答

//
// listproblem2.java : リストで遊ぼう (2)
//
//                     Copyright (C) 2017-2021 Makoto Hiroi
//
import java.util.List;
import java.util.function.Function;
import java.util.function.Predicate;
import immutable.ImList;
import immutable.LazyStream;
import immutable.Pair;
import immutable.Queue;

public class listproblem2 {
  // Q01
  static ImList<Double> height = ImList.of(
    148.7, 149.5, 133.7, 157.9, 154.2, 147.8, 154.6, 159.1, 148.2, 153.1,
    138.2, 138.7, 143.5, 153.2, 150.2, 157.3, 145.1, 157.2, 152.3, 148.3,
    152.0, 146.0, 151.5, 139.4, 158.8, 147.6, 144.0, 145.8, 155.4, 155.5,
    153.6, 138.5, 147.1, 149.6, 160.9, 148.9, 157.5, 155.1, 138.9, 153.0,
    153.9, 150.9, 144.4, 160.3, 153.4, 163.0, 150.9, 153.3, 146.6, 153.3,
    152.3, 153.3, 142.8, 149.0, 149.4, 156.5, 141.7, 146.2, 151.0, 156.5,
    150.8, 141.0, 149.0, 163.2, 144.1, 147.1, 167.9, 155.3, 142.9, 148.7,
    164.8, 154.1, 150.4, 154.2, 161.4, 155.0, 146.8, 154.2, 152.7, 149.7,
    151.5, 154.5, 156.8, 150.3, 143.2, 149.5, 145.6, 140.4, 136.5, 146.9,
    158.9, 144.4, 148.1, 155.5, 152.4, 153.3, 142.3, 155.3, 153.1, 152.3);

  static <E extends Comparable<E>> E maximum(ImList<E> xs) {
    return xs.rest().foldLeft((a, x) -> a.compareTo(x) > 0 ? a : x, xs.first());
  }

  static <E extends Comparable<E>> E minimum(ImList<E> xs) {
    return xs.rest().foldLeft((a, x) -> a.compareTo(x) < 0 ? a : x, xs.first());
  }

  static double sum(ImList<Double> xs) {
    return xs.foldLeft((a, x) -> a + x, 0.0);
  }

  static ImList<Double> average(ImList<Double> xs) {
    // return sum(xs) / xs.length();
    double a = 0.0;
    int c = 0;
    for (double x: xs) {
      a += x;
      c++;
    }
    return ImList.of(a, a / c);
  }

  static ImList<Double> avgSd(ImList<Double> xs) {
    double m = 0.0, s = 0.0;
    int i = 0;
    for (double x: xs) {
      i++;
      x -= m;
      m += x / i;
      s += (i - 1) * x * x / i;
    }
    return ImList.of(m, Math.sqrt(s / i));
  }

  // Q02
  static void pascal(int n) {
    var xs = ImList.of(1);
    while (n-- > 0) {
      System.out.println(xs);
      xs = ImList.zipWith((a, b) -> a + b, xs.append(ImList.of(0)), ImList.cons(0, xs));
    }
  }

  // Q03
  static <E> Pair<ImList<E>, ImList<E>> span(Predicate<E> pred, ImList<E> xs) {
    if (xs.isEmpty() || !pred.test(xs.first())) {
      return Pair.pair(ImList.nil(), xs);
    } else {
      var p = span(pred, xs.rest());
      return Pair.pair(ImList.cons(xs.first(), p.getFst()), p.getSnd());
    }
  }
  
  static <E> ImList<ImList<E>> pack(ImList<E> xs) {
    if (xs.isEmpty()) {
      return ImList.nil();
    } else {
      E x = xs.first();
      var p = span(y -> x.equals(y), xs);
      return ImList.cons(p.getFst(), pack(p.getSnd()));
    }
  }
  
  static <E> ImList<Pair<E, Integer>> encode(ImList<E> xs) {
    //return pack(xs).map(ys -> Pair.pair(ys.first(), ys.length()));
    if (xs.isEmpty()) return ImList.nil();
    E x = xs.first();
    var ys = xs.takeWhile(y -> x.equals(y));
    return ImList.cons(Pair.pair(x, ys.length()), encode(xs.dropWhile(y -> x.equals(y))));
    
  }

  static <E> ImList<E> decode(ImList<Pair<E, Integer>> xs) {
    return xs.flatMap(p -> ImList.fill(p.getSnd(), p.getFst()));
  }

  // 遅延ストリーム版
  static <E> LazyStream<Pair<E, Integer>> encodeLazy(LazyStream<E> xs) {
    if (xs.isEmpty()) return LazyStream.nil();
    E x = xs.first();
    var ys = xs.takeWhile(y -> x.equals(y));
    return LazyStream.cons(Pair.pair(x, ys.size()), () -> encodeLazy(xs.dropWhile(y -> x.equals(y))));
  }

  static <E> LazyStream<E> decodeLazy(LazyStream<Pair<E, Integer>> xs) {
    return xs.flatMap(p -> LazyStream.fill(p.getSnd(), p.getFst()));
  }

  // Q04
  //   B----D----F
  //  /|    |
  // A |    |
  //  \|    |
  //   C----E----G
  static enum Node { A, B, C, D, E, F, G }

  // 隣接リスト (連想リストになっている)
  static ImList<ImList<Node>> adjacent = ImList.of(
    ImList.of(Node.A, Node.B, Node.C),
    ImList.of(Node.B, Node.A, Node.C, Node.D),
    ImList.of(Node.C, Node.A, Node.B, Node.E),
    ImList.of(Node.D, Node.B, Node.E, Node.F),
    ImList.of(Node.E, Node.C, Node.D, Node.G),
    ImList.of(Node.F, Node.D),
    ImList.of(Node.G, Node.E));

  // 連想リストの探索
  static <E> ImList<E> assoc(E a, ImList<ImList<E>> xs) {
    var ys = xs.memberIf(x -> x.first() == a);
    return ys.isEmpty() ? ImList.nil() : ys.first().rest();
  }

  // 深さ優先探索
  static void depthFirstSearch(Node goal, ImList<Node> path) {
    if (path.first() == goal)
      System.out.println(path.reverse());
    else
      assoc(path.first(), adjacent).forEach(x -> {
        if (!path.contains(x))
          depthFirstSearch(goal, ImList.cons(x, path));
      });
  }

  // 幅優先探索
  static void breadthFirstSearch(Node start, Node goal) {
    Queue<ImList<Node>> q = Queue.queue();
    q = q.add(ImList.of(start));
    while (!q.isEmpty()) {
      var path = q.first();
      q = q.rest();
      if (path.first() == goal)
        System.out.println(path.reverse());
      else
        for (Node x: assoc(path.first(), adjacent)) {
          if (!path.contains(x))
            q = q.add(ImList.cons(x, path));
        }
    }
  }

  // 再帰版
  static void bfsRec(Queue<ImList<Node>> q, Node goal) {
    if (!q.isEmpty()) {
      var path = q.first();
      if (path.first() == goal) {
        System.out.println(path.reverse());
        bfsRec(q.rest(), goal);
      } else {
        bfsRec(assoc(path.first(), adjacent).foldLeft((newQ, x) -> {
          return path.contains(x) ? newQ : newQ.add(ImList.cons(x, path));
        }, q.rest()), goal);
      }
    }
  }

  // 反復深化
  static void dfs(Node goal, ImList<Node> path, int limit) {
    if (path.length() == limit) {
      if (path.first() == goal)
        System.out.println(path.reverse());
    } else {
      assoc(path.first(), adjacent).forEach(x -> {
        if (!path.contains(x))
          dfs(goal, ImList.cons(x, path), limit);
      });
    }
  }

  static void ids(Node start, Node goal) {
    for (int limit = 1; limit <= 7; limit++) {
      System.out.println("----- " + limit + " -----");
      dfs(goal, ImList.of(start), limit);
    }
  }

  // Q05
  static <E> ImList<Pair<E, ImList<E>>> select(ImList<E> xs) {
    if (xs.rest().isEmpty())
      return ImList.cons(Pair.pair(xs.first(), ImList.nil()), ImList.nil());
    else
      return ImList.cons(Pair.pair(xs.first(), xs.rest()),
                         select(xs.rest()).map(p -> Pair.pair(p.getFst(), ImList.cons(xs.first(), p.getSnd()))));
  }

  static boolean attack(int x, ImList<Integer> qs) {
    int n = 1;
    for (int y: qs) {
      if (x == y + n || x == y - n) return true;
      n++;
    }
    return false;
  }
  
  static void nqueens(ImList<Integer> xs, ImList<Integer> qs) {
    if (xs.isEmpty())
      System.out.println(qs.reverse());
    else
      select(xs).forEach(p -> {
        int x = p.getFst();
        if (!attack(x, qs)) nqueens(p.getSnd(), ImList.cons(x, qs));
      });
  }

  // Q06
  static final int farmer  = 0x01;
  static final int goat    = 0x02;
  static final int wolf    = 0x04;
  static final int cabbage = 0x08;

  // 同じ岸にいるか
  static boolean isSameSide(int xs, int x, int y) {
    return ((xs & x) == 0) == ((xs & y) == 0);
  }

  // 移動
  static int moveFarmer(int xs) {
    return xs ^ farmer;
  }

  static int moveGoat(int xs) {
    if (!isSameSide(xs, farmer, goat)) return -1;
    return (xs ^ farmer) ^ goat;
  }

  static int moveWolf(int xs) {
    if (!isSameSide(xs, farmer, wolf)) return -1;
    return (xs ^ farmer) ^ wolf;
  }

  static int moveCabbage(int xs) {
    if (!isSameSide(xs, farmer, cabbage)) return -1;
    return (xs ^ farmer) ^ cabbage;
  }

  // 移動関数表
  static ImList<Function<Integer, Integer>> moveFunc = ImList.of(
    listproblem2::moveFarmer,
    listproblem2::moveGoat,
    listproblem2::moveWolf,
    listproblem2::moveCabbage);
  
  // 安全か？
  static boolean isSafe(int xs) {
    if (!isSameSide(xs, farmer, goat) && isSameSide(xs, goat, wolf)) return false;
    if (!isSameSide(xs, farmer, cabbage) && isSameSide(xs, goat, cabbage)) return false;
    return true;
  }

  // 手順の表示
  static void printMove(ImList<Integer> xs) {
    for (int x: xs) {
      for (int i = 0; i < 2; i++) {
        System.out.print("[ ");
        if ((x & 1) == i) System.out.print("farmer ");
        if (((x >> 1) & 1) == i) System.out.print("goat ");
        if (((x >> 2) & 1) == i) System.out.print("wolf ");
        if (((x >> 3) & 1) == i) System.out.print("cabbage ");
        System.out.print("]");
      }
      System.out.println("");
    }
  }

  // 幅優先探索
  static void riverCrossing() {
    Queue<ImList<Integer>> q = Queue.queue();
    q = q.add(ImList.of(0));
    while (!q.isEmpty()) {
      var move = q.first();
      q = q.rest();
      int st = move.first();
      if (st == 0x0f) {
        printMove(move.reverse());
        return;
      } else {
        for (Function<Integer, Integer> func: moveFunc) {
          int newSt = func.apply(st);
          if (newSt != -1 && isSafe(newSt) && !move.contains(newSt)) {
            q = q.add(ImList.cons(newSt, move));
          }
        }
      }
    }
  }

  // Q07
  static ImList<ImList<Integer>> derangementSub(int m, ImList<Integer> xs) {
    if (xs.isEmpty())
      return ImList.of(ImList.nil());
    else
      return xs.filter(x -> x != m)
        .flatMap(x -> derangementSub(m + 1, xs.filter(y -> x != y)).map(ys -> ImList.cons(x, ys)));
  }

  static ImList<ImList<Integer>> derangement(int n) {
    return derangementSub(1, ImList.iota(1, n));
  }

  // Q08
  static <E> void partSetSub(ImList<E> xs, ImList<ImList<E>> a) {
    if (xs.isEmpty()) {
      System.out.println(a);
    } else {
      a.forEach(ys -> partSetSub(xs.rest(), ImList.cons(ImList.cons(xs.first(), ys), a.filter(zs -> zs != ys))));
      partSetSub(xs.rest(), ImList.cons(ImList.of(xs.first()), a));
    }
  }
  
  static <E> void partitionOfSet(ImList<E> xs) {
    partSetSub(xs.reverse(), ImList.nil());
  }

  // Q09
  static <E> void groupPartSub(int n, int m, ImList<E> xs, ImList<ImList<E>> a) {
    if (xs.isEmpty()) {
      System.out.println(a);
    } else {
      a.forEach(ys -> {
        if (ys.length() < n)
          groupPartSub(n, m, xs.rest(), ImList.cons(ImList.cons(xs.first(), ys), a.filter(zs -> zs != ys)));
      });
      if (a.length() < m)
        groupPartSub(n, m, xs.rest(), ImList.cons(ImList.of(xs.first()), a));
    }
  }
  
  static <E> void groupPartition(int n, int m, ImList<E> xs) {
    groupPartSub(n, m, xs.reverse(), ImList.nil());
  }

  // Q10
  static void partInt(int n, int k, ImList<Integer> a) {
    if (n == 0) {
      System.out.println(a);
    } else if (n == 1) {
      System.out.println(a.append(ImList.of(1)));
    } else if (k == 1) {
      System.out.println(a.append(ImList.fill(n, 1)));
    } else {
      if (n - k >= 0)
        partInt(n - k, k, a.append(ImList.of(k)));
      partInt(n, k - 1, a);
    }
  }
      
  static void partitionOfInt(int n) {
    partInt(n, n, ImList.nil());
  }
  
  public static void main(String[] args) {
    System.out.println("----- Q01 -----");
    System.out.println("min = " + minimum(height));
    System.out.println("max = " + maximum(height));
    System.out.println("sum = " + sum(height));
    System.out.println("(sum, avg) = " + average(height));
    System.out.println("(avg, sd) = " + avgSd(height));
    System.out.println("----- Q02 -----");
    pascal(16);
    System.out.println("----- Q03 -----");
    var xs = ImList.of(1,2,2,3,3,3,4,4,4,4,5,5,5,5,5);
    var ys = encode(xs);
    System.out.println(ys);
    System.out.println(decode(ys));
    var xs1 = LazyStream.of(xs);
    var ys1 = encodeLazy(xs1);
    ys1.forEach(System.out::print);
    System.out.println("");
    decodeLazy(ys1).forEach(c -> System.out.print(c + " "));
    System.out.println("");
    System.out.println("----- Q04 -----");
    System.out.println("----- dfs -----");
    depthFirstSearch(Node.G, ImList.of(Node.A));
    System.out.println("----- bfs -----");
    breadthFirstSearch(Node.A, Node.G);
    System.out.println("----- bfsRec -----");
    Queue<ImList<Node>> q = Queue.queue();
    bfsRec(q.add(ImList.of(Node.A)), Node.G);
    System.out.println("----- ids -----");
    ids(Node.A, Node.G);
    System.out.println("----- Q05 -----");
    for (int i = 4; i <= 8; i++)
      nqueens(ImList.iota(1, i), ImList.nil());
    System.out.println("----- Q06 -----");
    riverCrossing();
    System.out.println("----- Q07 -----");
    System.out.println(derangement(3));
    System.out.println(derangement(4));
    System.out.println(derangement(5));
    System.out.println("----- Q08 -----");
    partitionOfSet(ImList.iota(1, 3));
    partitionOfSet(ImList.iota(1, 4));
    System.out.println("----- Q09 -----");
    groupPartition(2, 2, ImList.iota(1, 4));
    groupPartition(3, 2, ImList.iota(1, 6));
    System.out.println("----- Q10 -----");
    partitionOfInt(5);
    partitionOfInt(6);
  }
}

●実行結果

----- Q01 -----
min = 133.7
max = 167.9
sum = 15062.699999999997
(sum, avg) = (15062.699999999997 150.62699999999998)
(avg, sd) = (150.62699999999998 6.433472701426506)
----- Q02 -----
(1)
(1 1)
(1 2 1)
(1 3 3 1)
(1 4 6 4 1)
(1 5 10 10 5 1)
(1 6 15 20 15 6 1)
(1 7 21 35 35 21 7 1)
(1 8 28 56 70 56 28 8 1)
(1 9 36 84 126 126 84 36 9 1)
(1 10 45 120 210 252 210 120 45 10 1)
(1 11 55 165 330 462 462 330 165 55 11 1)
(1 12 66 220 495 792 924 792 495 220 66 12 1)
(1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1)
(1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1)
(1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1)
----- Q03 -----
((1, 1) (2, 2) (3, 3) (4, 4) (5, 5))
(1 2 2 3 3 3 4 4 4 4 5 5 5 5 5)
(1, 1)(2, 2)(3, 3)(4, 4)(5, 5)
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 
----- Q04 -----
----- dfs -----
(A B C E G)
(A B D E G)
(A C B D E G)
(A C E G)
----- bfs -----
(A C E G)
(A B C E G)
(A B D E G)
(A C B D E G)
----- bfsRec -----
(A C E G)
(A B C E G)
(A B D E G)
(A C B D E G)
----- ids -----
----- 1 -----
----- 2 -----
----- 3 -----
----- 4 -----
(A C E G)
----- 5 -----
(A B C E G)
(A B D E G)
----- 6 -----
(A C B D E G)
----- 7 -----
----- Q05 -----
(2 4 1 3)
(3 1 4 2)
(1 3 5 2 4)
(1 4 2 5 3)
(2 4 1 3 5)
(2 5 3 1 4)
(3 1 4 2 5)
(3 5 2 4 1)
(4 1 3 5 2)
(4 2 5 3 1)
(5 2 4 1 3)
(5 3 1 4 2)
(2 4 6 1 3 5)
(3 6 2 5 1 4)
(4 1 5 2 6 3)
(5 3 1 6 4 2)
(1 3 5 7 2 4 6)
(1 4 7 3 6 2 5)
(1 5 2 6 3 7 4)
(1 6 4 2 7 5 3)
(2 4 1 7 5 3 6)
(2 4 6 1 3 5 7)
(2 5 1 4 7 3 6)
(2 5 3 1 7 4 6)
(2 5 7 4 1 3 6)
(2 6 3 7 4 1 5)
(2 7 5 3 1 6 4)
(3 1 6 2 5 7 4)
(3 1 6 4 2 7 5)
(3 5 7 2 4 6 1)
(3 6 2 5 1 4 7)
(3 7 2 4 6 1 5)
(3 7 4 1 5 2 6)
(4 1 3 6 2 7 5)
(4 1 5 2 6 3 7)
(4 2 7 5 3 1 6)
(4 6 1 3 5 7 2)
(4 7 3 6 2 5 1)
(4 7 5 2 6 1 3)
(5 1 4 7 3 6 2)
(5 1 6 4 2 7 3)
(5 2 6 3 7 4 1)
(5 3 1 6 4 2 7)
(5 7 2 4 6 1 3)
(5 7 2 6 3 1 4)
(6 1 3 5 7 2 4)
(6 2 5 1 4 7 3)
(6 3 1 4 7 5 2)
(6 3 5 7 1 4 2)
(6 3 7 4 1 5 2)
(6 4 2 7 5 3 1)
(6 4 7 1 3 5 2)
(7 2 4 6 1 3 5)
(7 3 6 2 5 1 4)
(7 4 1 5 2 6 3)
(7 5 3 1 6 4 2)
(1 5 8 6 3 7 2 4)
(1 6 8 3 7 4 2 5)
(1 7 4 6 8 2 5 3)
(1 7 5 8 2 4 6 3)
(2 4 6 8 3 1 7 5)
(2 5 7 1 3 8 6 4)
(2 5 7 4 1 8 6 3)
(2 6 1 7 4 8 3 5)
(2 6 8 3 1 4 7 5)
(2 7 3 6 8 5 1 4)
(2 7 5 8 1 4 6 3)
(2 8 6 1 3 5 7 4)
(3 1 7 5 8 2 4 6)
(3 5 2 8 1 7 4 6)
(3 5 2 8 6 4 7 1)
(3 5 7 1 4 2 8 6)
(3 5 8 4 1 7 2 6)
(3 6 2 5 8 1 7 4)
(3 6 2 7 1 4 8 5)
(3 6 2 7 5 1 8 4)
(3 6 4 1 8 5 7 2)
(3 6 4 2 8 5 7 1)
(3 6 8 1 4 7 5 2)
(3 6 8 1 5 7 2 4)
(3 6 8 2 4 1 7 5)
(3 7 2 8 5 1 4 6)
(3 7 2 8 6 4 1 5)
(3 8 4 7 1 6 2 5)
(4 1 5 8 2 7 3 6)
(4 1 5 8 6 3 7 2)
(4 2 5 8 6 1 3 7)
(4 2 7 3 6 8 1 5)
(4 2 7 3 6 8 5 1)
(4 2 7 5 1 8 6 3)
(4 2 8 5 7 1 3 6)
(4 2 8 6 1 3 5 7)
(4 6 1 5 2 8 3 7)
(4 6 8 2 7 1 3 5)
(4 6 8 3 1 7 5 2)
(4 7 1 8 5 2 6 3)
(4 7 3 8 2 5 1 6)
(4 7 5 2 6 1 3 8)
(4 7 5 3 1 6 8 2)
(4 8 1 3 6 2 7 5)
(4 8 1 5 7 2 6 3)
(4 8 5 3 1 7 2 6)
(5 1 4 6 8 2 7 3)
(5 1 8 4 2 7 3 6)
(5 1 8 6 3 7 2 4)
(5 2 4 6 8 3 1 7)
(5 2 4 7 3 8 6 1)
(5 2 6 1 7 4 8 3)
(5 2 8 1 4 7 3 6)
(5 3 1 6 8 2 4 7)
(5 3 1 7 2 8 6 4)
(5 3 8 4 7 1 6 2)
(5 7 1 3 8 6 4 2)
(5 7 1 4 2 8 6 3)
(5 7 2 4 8 1 3 6)
(5 7 2 6 3 1 4 8)
(5 7 2 6 3 1 8 4)
(5 7 4 1 3 8 6 2)
(5 8 4 1 3 6 2 7)
(5 8 4 1 7 2 6 3)
(6 1 5 2 8 3 7 4)
(6 2 7 1 3 5 8 4)
(6 2 7 1 4 8 5 3)
(6 3 1 7 5 8 2 4)
(6 3 1 8 4 2 7 5)
(6 3 1 8 5 2 4 7)
(6 3 5 7 1 4 2 8)
(6 3 5 8 1 4 2 7)
(6 3 7 2 4 8 1 5)
(6 3 7 2 8 5 1 4)
(6 3 7 4 1 8 2 5)
(6 4 1 5 8 2 7 3)
(6 4 2 8 5 7 1 3)
(6 4 7 1 3 5 2 8)
(6 4 7 1 8 2 5 3)
(6 8 2 4 1 7 5 3)
(7 1 3 8 6 4 2 5)
(7 2 4 1 8 5 3 6)
(7 2 6 3 1 4 8 5)
(7 3 1 6 8 5 2 4)
(7 3 8 2 5 1 6 4)
(7 4 2 5 8 1 3 6)
(7 4 2 8 6 1 3 5)
(7 5 3 1 6 8 2 4)
(8 2 4 1 7 5 3 6)
(8 2 5 3 1 7 4 6)
(8 3 1 6 2 5 7 4)
(8 4 1 3 6 2 7 5)
----- Q06 -----
[ farmer goat wolf cabbage ][ ]
[ wolf cabbage ][ farmer goat ]
[ farmer wolf cabbage ][ goat ]
[ cabbage ][ farmer goat wolf ]
[ farmer goat cabbage ][ wolf ]
[ goat ][ farmer wolf cabbage ]
[ farmer goat ][ wolf cabbage ]
[ ][ farmer goat wolf cabbage ]
----- Q07 -----
((2 3 1) (3 1 2))
((2 1 4 3) (2 3 4 1) (2 4 1 3) (3 1 4 2) (3 4 1 2) (3 4 2 1) (4 1 2 3) (4 3 1 2) (4 3 2 1))
((2 1 4 5 3) (2 1 5 3 4) (2 3 1 5 4) (2 3 4 5 1) (2 3 5 1 4) (2 4 1 5 3) (2 4 5 1 3) 
 (2 4 5 3 1) (2 5 1 3 4) (2 5 4 1 3) (2 5 4 3 1) (3 1 2 5 4) (3 1 4 5 2) (3 1 5 2 4) 
 (3 4 1 5 2) (3 4 2 5 1) (3 4 5 1 2) (3 4 5 2 1) (3 5 1 2 4) (3 5 2 1 4) (3 5 4 1 2) 
 (3 5 4 2 1) (4 1 2 5 3) (4 1 5 2 3) (4 1 5 3 2) (4 3 1 5 2) (4 3 2 5 1) (4 3 5 1 2) 
 (4 3 5 2 1) (4 5 1 2 3) (4 5 1 3 2) (4 5 2 1 3) (4 5 2 3 1) (5 1 2 3 4) (5 1 4 2 3) 
 (5 1 4 3 2) (5 3 1 2 4) (5 3 2 1 4) (5 3 4 1 2) (5 3 4 2 1) (5 4 1 2 3) (5 4 1 3 2) 
 (5 4 2 1 3) (5 4 2 3 1))
----- Q08 -----
((1 2 3))
((1) (2 3))
((1 2) (3))
((1 3) (2))
((1) (2) (3))
((1 2 3 4))
((1) (2 3 4))
((1 2) (3 4))
((1 3 4) (2))
((1) (2) (3 4))
((1 2 3) (4))
((1 4) (2 3))
((1) (2 3) (4))
((1 2 4) (3))
((1 3) (2 4))
((1) (2 4) (3))
((1 2) (3) (4))
((1 3) (2) (4))
((1 4) (2) (3))
((1) (2) (3) (4))
----- Q09 -----
((1 2) (3 4))
((1 4) (2 3))
((1 3) (2 4))
((1 2 3) (4 5 6))
((1 5 6) (2 3 4))
((1 3 4) (2 5 6))
((1 2 4) (3 5 6))
((1 2 6) (3 4 5))
((1 4 5) (2 3 6))
((1 3 6) (2 4 5))
((1 2 5) (3 4 6))
((1 4 6) (2 3 5))
((1 3 5) (2 4 6))
----- Q10 -----
(5)
(4 1)
(3 2)
(3 1 1)
(2 2 1)
(2 1 1 1)
(1 1 1 1 1)
(6)
(5 1)
(4 2)
(4 1 1)
(3 3)
(3 2 1)
(3 1 1 1)
(2 2 2)
(2 2 1 1)
(2 1 1 1 1)
(1 1 1 1 1 1)
初版 2017 年 1 月 2 日
改訂 2021 年 2 月 28 日