commit a80e95e4f3ed8566c3d118258ed3bcbbc465e3dd
Author: Leszek Koltunski <leszek@koltunski.pl>
Date:   Tue May 23 00:48:59 2023 +0200

    implement enumeration of permutations in linear time. This hopefully speeds up all solvers.

diff --git a/src/main/java/org/distorted/objectlib/tablebases/TBDino4.java b/src/main/java/org/distorted/objectlib/tablebases/TBDino4.java
index fc71ea26..9f34518e 100644
--- a/src/main/java/org/distorted/objectlib/tablebases/TBDino4.java
+++ b/src/main/java/org/distorted/objectlib/tablebases/TBDino4.java
@@ -222,7 +222,7 @@ public class TBDino4 extends TBDino
     fillPerm(perm,partition,2);
     fillPerm(perm,partition,3);
 
-    return TBDino6.getQuatsFromPerm(perm);
+    return TBDino.getQuatsFromPerm(perm);
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
@@ -231,7 +231,7 @@ public class TBDino4 extends TBDino
     {
     int[] perm = new int[12];
     System.arraycopy(quats, 0, perm, 0, 12);
-    TBDino6.getPermFromQuats(perm);
+    TBDino.getPermFromQuats(perm);
 
     int[] part = new int[12];
 
diff --git a/src/main/java/org/distorted/objectlib/tablebases/TBDino6.java b/src/main/java/org/distorted/objectlib/tablebases/TBDino6.java
index fdb0422e..11be893c 100644
--- a/src/main/java/org/distorted/objectlib/tablebases/TBDino6.java
+++ b/src/main/java/org/distorted/objectlib/tablebases/TBDino6.java
@@ -17,7 +17,7 @@ import org.distorted.objectlib.helpers.OperatingSystemInterface;
 public class TBDino6 extends TBDino
 {
   private static final int SOLVED1 =        0;
-  private static final int SOLVED2 = 13379863; // quats (0,10,0,10, 11,11,11,11, 0,10,0,10)
+  private static final int SOLVED2 = 17977621; // quats (0,10,0,10, 11,11,11,11, 0,10,0,10)
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
diff --git a/src/main/java/org/distorted/objectlib/tablebases/TablebaseHelpers.java b/src/main/java/org/distorted/objectlib/tablebases/TablebaseHelpers.java
index f0df778f..7d5e530f 100644
--- a/src/main/java/org/distorted/objectlib/tablebases/TablebaseHelpers.java
+++ b/src/main/java/org/distorted/objectlib/tablebases/TablebaseHelpers.java
@@ -79,62 +79,66 @@ public class TablebaseHelpers
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  public static void test2(TablebasesAbstract tb, int num)
-    {
-    Random rnd = new Random();
-    int size = tb.getSize();
+  private final static int MAX_PERM=12;  // biggest N for which N! is still less than 2^32
+  private final static int[] avail = new int[MAX_PERM];
+  private final static int[] pos   = new int[MAX_PERM];
+  private final static int[] fact  = new int[MAX_PERM];
 
-    for(int i=0; i<num; i++)
-      {
-      int next = rnd.nextInt(size-1);
-      int[][] moves = tb.solution(next,null,null);
-      String moveSeq = print(moves);
-      android.util.Log.e("D", (moves==null ? 0 : moves.length)+" Trying "+next+" : "+moveSeq);
-      }
-    }
+  static
+    {
+    fact[0] = 1;
+    for(int i=1; i<MAX_PERM; i++) fact[i] = fact[i-1]*i;
+    };
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private static int swaps(int val, int[] buffer, int len)
+  public static void getPermutationFromNum(int[] buffer,int permSize, int permNum)
     {
-    int ret = 0;
+    avail[0] = pos[0] = 0;
+    for(int i=1; i<permSize; i++) avail[i] = pos[i] = permSize-i;
 
-    for(int i=0; i<len; i++)
+    for(int i=0; i<permSize-1; i++)
       {
-           if( buffer[i] >val ) ret++;
-      else if( buffer[i]==val ) return ret;
+      int m = fact[permSize-1-i];
+      int k = permNum/m;
+      permNum %= m;
+      buffer[i] = avail[k];
+      int y = avail[permSize-1-i];
+      pos[y] = k;
+      avail[k] = y;
       }
 
-    return -1;
+    buffer[permSize-1] = avail[0];
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
-
-  public static boolean permutationIsEven(int[] buffer)
+// Enumeration of permutations in linear time.
+// 1) notice that 'avail' and 'pos' are always inverses: avail[m]=n iff pos[n]=m
+// 2) notice that that implies that after the i-th execution of the loop, avail[0 ... n-1-i]
+//    contains the n-i elements of the permutation we haven't scanned yet
+//    ( that is because this is true initially, and during each loop, we remove avail[k] from
+//      this list - but k = pos[buffer[i]] implies buffer[i] = avail[k] so we are really removing
+//      buffer[i] - i.e. exactly the permutation element we have just scanned! )
+// 3) each 'k' is a digit of the permutation in a strange ( n-1,n-2,...,2 ) notation where the most
+//    significant digit can be one of the {0...,n-1}, the next most significant - one of the {0,...,n-2},
+//    etc.
+// 4) the ret = ret*(permSize-i) + k is a transform from this ( n-1,n-2,...,2 ) notation to an index.
+
+  public static int computePermutationNum(int[] buffer)
     {
-    int len = buffer.length;
-    int numOfSwaps = 0;
-    for(int i=0; i<len-1; i++) numOfSwaps += swaps(i,buffer,len);
-    return (numOfSwaps%2==0);
-    }
-
-///////////////////////////////////////////////////////////////////////////////////////////////////
+    int permSize = buffer.length;
+    avail[0] = pos[0] = 0;
+    for(int i=1; i<permSize; i++) avail[i] = pos[i] = permSize-i;
 
-  public static int computeEvenPermutationNum(int[] permutation)
-    {
-    int len = permutation.length-2;
     int ret = 0;
-    int mul = 4;
 
-    for(int i=0; i<len; i++)
+    for(int i=0; i<permSize-1; i++)
       {
-      ret += swaps(len-1-i,permutation,len+2);
-
-      if( i<len-1 )
-        {
-        ret *= mul;
-        mul++;
-        }
+      int k = pos[buffer[i]];
+      ret = ret*(permSize-i) + k;
+      int y = avail[permSize-1-i];
+      pos[y] = k;
+      avail[k] = y;
       }
 
     return ret;
@@ -142,122 +146,44 @@ public class TablebaseHelpers
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  public static void getEvenPermutationFromNum(int[] buffer, int permNum)
+  public static int computeEvenPermutationNum(int[] buffer)
     {
-    int permSize = buffer.length;
-    int index = permSize;
-    int len = permSize-2;
-    int totalSwaps = 0;
-
-    for(int i=0; i<permSize; i++) buffer[i]=-1;
-
-    for(int i=0; i<len; i++)
-      {
-      int swaps = (permNum%index);
-      permNum /= index;
-      index--;
-      totalSwaps += swaps;
-
-      for(int j=0; j<permSize; j++)
-        {
-        if( buffer[j]==-1 )
-          {
-          if( swaps==0 )
-            {
-            buffer[j] = i;
-            break;
-            }
-          swaps--;
-          }
-        }
-      }
-
-    int lower, upper;
-
-    if( (totalSwaps%2)==0 )
-      {
-      lower = permSize-2;
-      upper = permSize-1;
-      }
-    else
-      {
-      lower = permSize-1;
-      upper = permSize-2;
-      }
+    int index = computePermutationNum(buffer);
+    return index/2;
+    }
 
-    boolean first=true;
+///////////////////////////////////////////////////////////////////////////////////////////////////
 
-    for(int i=0; i<permSize; i++)
-      if( buffer[i]==-1 )
-        {
-        if( first )
-          {
-          buffer[i] = lower;
-          first=false;
-          }
-        else
-          {
-          buffer[i] = upper;
-          break;
-          }
-        }
+  public static void getEvenPermutationFromNum(int[] buffer, int permNum)
+    {
+    getPermutationFromNum(buffer, buffer.length, 2*permNum);
+    boolean even = permutationIsEven(buffer);
+    if( !even ) getPermutationFromNum(buffer, buffer.length, 2*permNum+1 );
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  public static int computePermutationNum(int[] permutation)
+  private static int swaps(int val, int[] buffer, int len)
     {
-    int len = permutation.length;
     int ret = 0;
-    int mul = 3;
 
-    for(int i=0; i<len-2; i++)
+    for(int i=0; i<len; i++)
       {
-      ret += swaps(len-2-i,permutation,len);
-      ret *= mul;
-      mul++;
+           if( buffer[i] >val ) ret++;
+      else if( buffer[i]==val ) return ret;
       }
 
-    ret += swaps(0,permutation,len);
-
-    return ret;
+    return -1;
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  public static void getPermutationFromNum(int[] buffer,int permSize, int permNum)
+  public static boolean permutationIsEven(int[] buffer)
     {
-    int index = permSize;
-    int len = permSize-1;
-
-    for(int i=0; i<permSize; i++) buffer[i]=-1;
-
-    for(int i=0; i<len; i++)
-      {
-      int swaps = (permNum%index);
-      permNum /= index;
-      index--;
-
-      for(int j=0; j<permSize; j++)
-        {
-        if( buffer[j]==-1 )
-          {
-          if( swaps==0 )
-            {
-            buffer[j] = i;
-            break;
-            }
-          swaps--;
-          }
-        }
-      }
-
-    for(int i=0; i<permSize; i++)
-      if( buffer[i]==-1 )
-        {
-        buffer[i] = permSize-1;
-        break;
-        }
+    int len = buffer.length;
+    int numOfSwaps = 0;
+    for(int i=0; i<len-1; i++) numOfSwaps += swaps(i,buffer,len);
+    return (numOfSwaps%2==0);
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
diff --git a/src/main/res/raw/cu_232_tablebase.db b/src/main/res/raw/cu_232_tablebase.db
index c9237404..f943213b 100644
Binary files a/src/main/res/raw/cu_232_tablebase.db and b/src/main/res/raw/cu_232_tablebase.db differ
diff --git a/src/main/res/raw/cu_323_pruning17.db b/src/main/res/raw/cu_323_pruning17.db
index f4c55a63..cae382bc 100644
Binary files a/src/main/res/raw/cu_323_pruning17.db and b/src/main/res/raw/cu_323_pruning17.db differ
diff --git a/src/main/res/raw/cu_323_pruning18.db b/src/main/res/raw/cu_323_pruning18.db
index 3753f4f0..efecc5ba 100644
Binary files a/src/main/res/raw/cu_323_pruning18.db and b/src/main/res/raw/cu_323_pruning18.db differ
diff --git a/src/main/res/raw/cu_323_pruning7.db b/src/main/res/raw/cu_323_pruning7.db
index 0475b478..1852a81f 100644
Binary files a/src/main/res/raw/cu_323_pruning7.db and b/src/main/res/raw/cu_323_pruning7.db differ
diff --git a/src/main/res/raw/cu_323_pruning8.db b/src/main/res/raw/cu_323_pruning8.db
index 20e5398e..d0235d80 100644
Binary files a/src/main/res/raw/cu_323_pruning8.db and b/src/main/res/raw/cu_323_pruning8.db differ
diff --git a/src/main/res/raw/cube_2_pruning11.db b/src/main/res/raw/cube_2_pruning11.db
index 6ec578cb..f8737c76 100644
Binary files a/src/main/res/raw/cube_2_pruning11.db and b/src/main/res/raw/cube_2_pruning11.db differ
diff --git a/src/main/res/raw/cube_2_pruning4.db b/src/main/res/raw/cube_2_pruning4.db
index c2c1258c..ff79f2e8 100644
Binary files a/src/main/res/raw/cube_2_pruning4.db and b/src/main/res/raw/cube_2_pruning4.db differ
diff --git a/src/main/res/raw/cube_2_pruning5.db b/src/main/res/raw/cube_2_pruning5.db
index 257b617f..99aa0d0a 100644
Binary files a/src/main/res/raw/cube_2_pruning5.db and b/src/main/res/raw/cube_2_pruning5.db differ
diff --git a/src/main/res/raw/diam_2_tablebase.db b/src/main/res/raw/diam_2_tablebase.db
index 81360b41..1ef7c5e3 100644
Binary files a/src/main/res/raw/diam_2_tablebase.db and b/src/main/res/raw/diam_2_tablebase.db differ
diff --git a/src/main/res/raw/dino_3_pruning10.db b/src/main/res/raw/dino_3_pruning10.db
index 60cb6b5c..8190c126 100644
Binary files a/src/main/res/raw/dino_3_pruning10.db and b/src/main/res/raw/dino_3_pruning10.db differ
diff --git a/src/main/res/raw/dino_3_pruning3.db b/src/main/res/raw/dino_3_pruning3.db
index 1368c15b..cd43ce8d 100644
Binary files a/src/main/res/raw/dino_3_pruning3.db and b/src/main/res/raw/dino_3_pruning3.db differ
diff --git a/src/main/res/raw/dino_3_pruning4.db b/src/main/res/raw/dino_3_pruning4.db
index ae66d535..0d5f658c 100644
Binary files a/src/main/res/raw/dino_3_pruning4.db and b/src/main/res/raw/dino_3_pruning4.db differ
diff --git a/src/main/res/raw/ivy_2_tablebase.db b/src/main/res/raw/ivy_2_tablebase.db
index 8622d24c..2a253c19 100644
Binary files a/src/main/res/raw/ivy_2_tablebase.db and b/src/main/res/raw/ivy_2_tablebase.db differ
diff --git a/src/main/res/raw/jing_2_pruning11.db b/src/main/res/raw/jing_2_pruning11.db
index 4106dd88..60973445 100644
Binary files a/src/main/res/raw/jing_2_pruning11.db and b/src/main/res/raw/jing_2_pruning11.db differ
diff --git a/src/main/res/raw/jing_2_pruning4.db b/src/main/res/raw/jing_2_pruning4.db
index 3fdce080..9b2b6c7c 100644
Binary files a/src/main/res/raw/jing_2_pruning4.db and b/src/main/res/raw/jing_2_pruning4.db differ
diff --git a/src/main/res/raw/jing_2_pruning5.db b/src/main/res/raw/jing_2_pruning5.db
index 197fc499..43f1176b 100644
Binary files a/src/main/res/raw/jing_2_pruning5.db and b/src/main/res/raw/jing_2_pruning5.db differ
diff --git a/src/main/res/raw/pdia_3_pruning3.db b/src/main/res/raw/pdia_3_pruning3.db
index ae9621ad..d926a253 100644
Binary files a/src/main/res/raw/pdia_3_pruning3.db and b/src/main/res/raw/pdia_3_pruning3.db differ
diff --git a/src/main/res/raw/pdia_3_pruning4.db b/src/main/res/raw/pdia_3_pruning4.db
index 7bae7a43..6dd58c07 100644
Binary files a/src/main/res/raw/pdia_3_pruning4.db and b/src/main/res/raw/pdia_3_pruning4.db differ
diff --git a/src/main/res/raw/pyra_3_tablebase.db b/src/main/res/raw/pyra_3_tablebase.db
index 31a8427f..45367422 100644
Binary files a/src/main/res/raw/pyra_3_tablebase.db and b/src/main/res/raw/pyra_3_tablebase.db differ
diff --git a/src/main/res/raw/skew_2_pruning11.db b/src/main/res/raw/skew_2_pruning11.db
index fef9e3ae..3676787e 100644
Binary files a/src/main/res/raw/skew_2_pruning11.db and b/src/main/res/raw/skew_2_pruning11.db differ
diff --git a/src/main/res/raw/skew_2_pruning4.db b/src/main/res/raw/skew_2_pruning4.db
index ab9467d7..681ef709 100644
Binary files a/src/main/res/raw/skew_2_pruning4.db and b/src/main/res/raw/skew_2_pruning4.db differ
diff --git a/src/main/res/raw/skew_2_pruning5.db b/src/main/res/raw/skew_2_pruning5.db
index 777648ff..9ed5b15f 100644
Binary files a/src/main/res/raw/skew_2_pruning5.db and b/src/main/res/raw/skew_2_pruning5.db differ
