fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.BitSet;
  4. import java.util.Collections;
  5. import java.util.concurrent.TimeUnit;
  6. import java.util.function.Consumer;
  7.  
  8. class BilliardsBall
  9. {
  10.     // 1～MAX_BALL_NUMBERの数が書かれた球を使う
  11.     static final int MAX_BALL_NUMBER = 15;
  12.  
  13.     public static void main(String[] args)
  14.     {
  15.         for(int i = 3; i <= 7; i++)
  16.             new BilliardsBall(i).print();
  17.     }
  18.  
  19.     private int n;
  20.     private int m;
  21.     private ArrayList<int[]> result = new ArrayList<int[]>();
  22.     private long time;
  23.  
  24.     BilliardsBall(int n)
  25.     {
  26.         long s = System.nanoTime();
  27.         this.n = n;
  28.         BitSet bit = new BitSet();
  29.         forEach(true, n, p -> {
  30.             bit.clear();
  31.  
  32.             int sum = 0;
  33.             for (int i = 0; i < p.length; i++)
  34.             {
  35.                 sum += p[i];
  36.             }
  37.             if (sum < m) return;
  38.             bit.set(sum);
  39.  
  40.             for (int i = 0; i < p.length; i++)
  41.             {
  42.                 sum = 0;
  43.                 for (int j = 0; j < p.length - 1; j++)
  44.                 {
  45.                     sum += p[(i + j) % p.length];
  46.                     bit.set(sum);
  47.                 }
  48.             }
  49.  
  50.             int max = bit.nextClearBit(1) - 1;
  51.             if (m <= max)
  52.             {
  53.                 if (m < max) result.clear();
  54.  
  55.                 int[] is = new int[p.length];
  56.                 for(int i = 0; i < p.length - 1; i++)
  57.                 {
  58.                     is[i] = p[i + 1];
  59.                 }
  60.                 is[p.length - 1] = p[0];
  61.                 result.add(is);
  62.                 m = max;
  63.             }
  64.         });
  65.  
  66.         Collections.sort(result, (int[] a, int[] b) -> {
  67.             int compare = 0;
  68.             for (int i = 0; i < n && compare == 0; i++)
  69.             {
  70.                 compare = Integer.compare(a[i], b[i]);
  71.             }
  72.             return compare;
  73.         });
  74.         long e = System.nanoTime();
  75.         time = TimeUnit.NANOSECONDS.toMillis(e - s);
  76.     }
  77.  
  78.     public void print()
  79.     {
  80.         System.out.printf("N=%d, M=%d, Time=%dms%n", n, m, time);
  81.         for(int[] is : result)
  82.         {
  83.             System.out.println(Arrays.toString(is));
  84.         }
  85.         System.out.println();
  86.     }
  87.  
  88.     /**
  89.      * 順列を生成してConsumerに処理を投げる
  90.      * @param reduce 計算量削減させるかどうか
  91.      * @param num 球の数
  92.      * @param c
  93.      */
  94.     static void forEach(boolean reduce, int num, Consumer<int[]> c)
  95.     {
  96.         if (num < 3 || num > MAX_BALL_NUMBER) throw new IllegalArgumentException();
  97.  
  98.         // 計算量削減のために最初3個をA,B,Cとした場合 B=1, C<Aとなるようにする。(基点の位置確定と反転の回避)
  99.         if (reduce)
  100.         {
  101.             int[] perm = new int[num];
  102.             boolean[] used = new boolean[MAX_BALL_NUMBER + 1];
  103.  
  104.             perm[1] = 1;
  105.             used[1] = true;
  106.             for (int i = 2; i <= MAX_BALL_NUMBER - 1; i++)
  107.             {
  108.                 perm[2] = i;
  109.                 used[i] = true;
  110.                 for (int j = i + 1; j <= MAX_BALL_NUMBER; j++)
  111.                 {
  112.                     perm[0] = j;
  113.                     used[j] = true;
  114.                     p(perm, used, 3, c);
  115.                     used[j] = false;
  116.                 }
  117.                 used[i] = false;
  118.             }
  119.         }
  120.         else
  121.         // 計算量削減せずに全パターン調べる
  122.         {
  123.             p(new int[num], new boolean[MAX_BALL_NUMBER + 1], 0, c);
  124.         }
  125.     }
  126.  
  127.     /**
  128.      * 再帰で順列生成
  129.      */
  130.     private static void p(int[] perm, boolean[] used, int p, Consumer<int[]> c)
  131.     {
  132.         if (perm.length == p)
  133.         {
  134.             c.accept(perm);
  135.             return;
  136.         }
  137.  
  138.         for (int i = 1; i <= MAX_BALL_NUMBER; i++)
  139.         {
  140.             if (used[i]) continue;
  141.             used[i] = true;
  142.             perm[p] = i;
  143.             p(perm, used, p + 1, c);
  144.             used[i] = false;
  145.         }
  146.     }
  147. }
Success #stdin #stdout 1.93s 320704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
N=3, M=7, Time=83ms
[1, 2, 4]

N=4, M=13, Time=4ms
[1, 2, 6, 4]
[1, 3, 2, 7]

N=5, M=21, Time=11ms
[1, 3, 10, 2, 5]

N=6, M=31, Time=127ms
[1, 2, 5, 4, 6, 13]
[1, 2, 7, 4, 12, 5]
[1, 3, 2, 7, 8, 10]
[1, 3, 6, 2, 5, 14]
[1, 7, 3, 2, 4, 14]

N=7, M=39, Time=1582ms
[1, 2, 8, 6, 13, 5, 4]
[1, 3, 14, 6, 5, 2, 8]
[1, 4, 2, 7, 3, 8, 14]
[1, 4, 3, 9, 2, 15, 5]
[1, 6, 2, 3, 13, 4, 10]
[1, 9, 3, 5, 2, 4, 15]
https://ideone.com/JjZwqQ
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!