Doing Partial Permutations on G'MIC (Solved)

Software G'MIC
1

As some of you know, I have made commands to try to mimic Python itertools. However, there’s only one thing that is noticeable which is missing, and that is partial permutation. There’s not much codes out there, so this remains unsolved.

This is what a partial permutation looks like:

perm = permutations(7, 3)

(0, 1, 2)
(0, 1, 3)
(0, 1, 4)
(0, 1, 5)
(0, 1, 6)
(0, 2, 1)
(0, 2, 3)
(0, 2, 4)
(0, 2, 5)
(0, 2, 6)
(0, 3, 1)
(0, 3, 2)
(0, 3, 4)
(0, 3, 5)
(0, 3, 6)
(0, 4, 1)
(0, 4, 2)
(0, 4, 3)
(0, 4, 5)
(0, 4, 6)
(0, 5, 1)
(0, 5, 2)
(0, 5, 3)
(0, 5, 4)
(0, 5, 6)
(0, 6, 1)
(0, 6, 2)
(0, 6, 3)
(0, 6, 4)
(0, 6, 5)
(1, 0, 2)
(1, 0, 3)
(1, 0, 4)
(1, 0, 5)
(1, 0, 6)
(1, 2, 0)
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 2, 6)
(1, 3, 0)
(1, 3, 2)
(1, 3, 4)
(1, 3, 5)
(1, 3, 6)
(1, 4, 0)
(1, 4, 2)
(1, 4, 3)
(1, 4, 5)
(1, 4, 6)
(1, 5, 0)
(1, 5, 2)
(1, 5, 3)
(1, 5, 4)
(1, 5, 6)
(1, 6, 0)
(1, 6, 2)
(1, 6, 3)
(1, 6, 4)
(1, 6, 5)
(2, 0, 1)
(2, 0, 3)
(2, 0, 4)
(2, 0, 5)
(2, 0, 6)
(2, 1, 0)
(2, 1, 3)
(2, 1, 4)
(2, 1, 5)
(2, 1, 6)
(2, 3, 0)
(2, 3, 1)
(2, 3, 4)
(2, 3, 5)
(2, 3, 6)
(2, 4, 0)
(2, 4, 1)
(2, 4, 3)
(2, 4, 5)
(2, 4, 6)
(2, 5, 0)
(2, 5, 1)
(2, 5, 3)
(2, 5, 4)
(2, 5, 6)
(2, 6, 0)
(2, 6, 1)
(2, 6, 3)
(2, 6, 4)
(2, 6, 5)
(3, 0, 1)
(3, 0, 2)
(3, 0, 4)
(3, 0, 5)
(3, 0, 6)
(3, 1, 0)
(3, 1, 2)
(3, 1, 4)
(3, 1, 5)
(3, 1, 6)
(3, 2, 0)
(3, 2, 1)
(3, 2, 4)
(3, 2, 5)
(3, 2, 6)
(3, 4, 0)
(3, 4, 1)
(3, 4, 2)
(3, 4, 5)
(3, 4, 6)
(3, 5, 0)
(3, 5, 1)
(3, 5, 2)
(3, 5, 4)
(3, 5, 6)
(3, 6, 0)
(3, 6, 1)
(3, 6, 2)
(3, 6, 4)
(3, 6, 5)
(4, 0, 1)
(4, 0, 2)
(4, 0, 3)
(4, 0, 5)
(4, 0, 6)
(4, 1, 0)
(4, 1, 2)
(4, 1, 3)
(4, 1, 5)
(4, 1, 6)
(4, 2, 0)
(4, 2, 1)
(4, 2, 3)
(4, 2, 5)
(4, 2, 6)
(4, 3, 0)
(4, 3, 1)
(4, 3, 2)
(4, 3, 5)
(4, 3, 6)
(4, 5, 0)
(4, 5, 1)
(4, 5, 2)
(4, 5, 3)
(4, 5, 6)
(4, 6, 0)
(4, 6, 1)
(4, 6, 2)
(4, 6, 3)
(4, 6, 5)
(5, 0, 1)
(5, 0, 2)
(5, 0, 3)
(5, 0, 4)
(5, 0, 6)
(5, 1, 0)
(5, 1, 2)
(5, 1, 3)
(5, 1, 4)
(5, 1, 6)
(5, 2, 0)
(5, 2, 1)
(5, 2, 3)
(5, 2, 4)
(5, 2, 6)
(5, 3, 0)
(5, 3, 1)
(5, 3, 2)
(5, 3, 4)
(5, 3, 6)
(5, 4, 0)
(5, 4, 1)
(5, 4, 2)
(5, 4, 3)
(5, 4, 6)
(5, 6, 0)
(5, 6, 1)
(5, 6, 2)
(5, 6, 3)
(5, 6, 4)
(6, 0, 1)
(6, 0, 2)
(6, 0, 3)
(6, 0, 4)
(6, 0, 5)
(6, 1, 0)
(6, 1, 2)
(6, 1, 3)
(6, 1, 4)
(6, 1, 5)
(6, 2, 0)
(6, 2, 1)
(6, 2, 3)
(6, 2, 4)
(6, 2, 5)
(6, 3, 0)
(6, 3, 1)
(6, 3, 2)
(6, 3, 4)
(6, 3, 5)
(6, 4, 0)
(6, 4, 1)
(6, 4, 2)
(6, 4, 3)
(6, 4, 5)
(6, 5, 0)
(6, 5, 1)
(6, 5, 2)
(6, 5, 3)
(6, 5, 4)

perm = permutations(4, 2)

(0, 1)
(0, 2)
(0, 3)
(1, 0)
(1, 2)
(1, 3)
(2, 0)
(2, 1)
(2, 3)
(3, 0)
(3, 1)
(3, 2)

Contrast that with my full permutations command:

rep_permutations 7

With the above code, you get 5040 permutations.

And the kicker? I have made tools to extract the location from the number, and to extract number from a location. It’s O(n) in terms of finding them as they don’t involve generating other permutations. If I have to generate other permutations, then it would be O(n!).

#@cli rep_extract_permutation_order: number_of_item,permutation_number
#@cli : Return permutation order at index permutation_number.

#@cli rep_find_permutation_lexicographic_index: number_list
#@cli : Return the lexicographic index in which this permutation is found within a list of all possible permutation.
#@cli :
#@cli : number_list must be in the form of 0,1,2,3.... , but can be in any order.

Here’s the result of those:

$ rep_permutations 7 echo {I[#-1,3000]} rm.
[gmic]-0./ Start G'MIC interpreter.
4,1,0,2,3,5,6
[gmic]-1./ Remove image [0] (0 images left).
[gmic]-0./ End G'MIC interpreter

$ echo ${rep_extract_permutation_order\ 7,3000}
4,1,0,2,3,5,6

$ echo ${rep_find_permutation_lexicographic_index\ 4,1,0,2,3,5,6}
3000

As you can see in the results, it works really well. It always do.

1 Like
2

Looks like there’s finally a code here: A Simple, Efficient P(n,k) Algorithm – Alistair Israel . Last search did not reveal that web page.

I can work with this to make partial permutation. However, doing the extra thing is going to present a interesting problem, but I’ll get to that later on.

3

Before I finish translating the Java code, I’d like to know if MIT is compatible with CeCiLL v.2.0. @David_Tschumperle

EDIT: I think I will do the pseudo-code provided there instead. No license concerns or anything.

EDIT: Nah, I don’t think I can do this.

This is my best attempt, but something is wrong and don’t know what:

EDIT: Finally nailed it!

I guess this can be considered solved.

#@cli rep_partial_permutations: number_of_items,selected_items_count,_axis={x|y|z}
#@cli : Generates partial combination. P(n,k)
#@cli : Note - Code is taken from Alistairisrael psuedo-code - https://alistairisrael.wordpress.com/2009/09/22/simple-efficient-pnk-algorithm/
#@cli : Default values: '_axis=x'
+rep_partial_permutations:
skip ${3=x}

check "($1>=$2&&$1>0&&isint($1))&&($2>0&&isint($2))&&inrange(_'$3',_'x',_'z',1,1)"

if [${1-2}]==[1,1] 1 return fi

num_of_combinations,axis={permut($2,$1,1)},{_'$3'-_'x'}

if $axis==2   out_dim=1,1,$num_of_combinations
elif $axis==1 out_dim=1,$num_of_combinations,1
else          out_dim=$num_of_combinations,1,1
fi

if $2==1 $out_dim,1,${arg\ $axis+1,x,y,z} return fi

$out_dim,$2,>"begin(
  const edge=s-1;
  const n=$1;
  const dec_n=n-1;
  const axis=$axis;
  
  axis==2?(
   axis()=z;
  ):
  axis==1?(
   axis()=y;
  ):(
   axis()=x;
  );
  
  output=expr('x',n);
  
  reverse_array_starting_from(a)=(
   start=a;
   end=dec_n;
   while(start<end,
    swap(output[start++],output[end--]);
   );
  );
  
 );
 
 if(axis(),
  
  j=s;
  while(j<n && (output[edge]>=output[j]),++j;);
 
  j<n?(
   swap(output[edge],output[j]);
  ):(
   reverse_array_starting_from(s);
  
   i=edge-1;
   while(i>=0 && output[i]>=output[i+1],--i;);
   
   j=dec_n;
   while(j>i && (output[i]>=output[j]),--j;);
  
   swap(output[i],output[j]);
  
   reverse_array_starting_from(i+1);
  );
 );
 
 (output)[0,s];
 "

EDIT: Now finished extract_partial_permutation_order too:

#@cli rep_extract_partial_permutation_order: number_of_item,selected_items_count,permutation_number
#@cli : Return permutation order at index permutation_number.
rep_extract_partial_permutation_order:

check "$2<=$1&&$1>0&&$2>0"

if $1==1 status 0
elif $2==1 status {$3%$1}
else

 permutation_number={$3%permut($2,$1,1)}

 1,{$1+1},1,1,y
 
 {1+($1==$2?$1-2:min($1-1,$2-1))},1,1,1,>"begin(
   const m=($1==$2?1:$1-$2)+1;
   v=m;
  );
  x>1?v=v*(m+x-1):(x?v:1);"
 
 eval "
  new_arr=vector(#$2,0);
  divisor_position=w#-1-1;
  permutation_number=$permutation_number;
  
  repeat(w#-1,iter,
   division_number=i[#-1,divisor_position];
   pos=int(permutation_number/division_number);
   new_arr_num=i[#-2,pos];
   new_arr[iter]=new_arr_num;
   da_remove(#-2,pos);
   permutation_number%=division_number;
   --divisor_position;
  );
  
  new_arr[iter]=i[#-2,0];
  new_arr;
  "
 
 remove[-2--1]
fi

Next one is a doozy though.