How To Improve Efficiency Of Algorithm Which Generates Next Lexicographic Permutation?
Solution 1:
TL;DR version
Unfortunately, the only way to improve performance of this algorithm is to get rid of it and use something better instead.
Are the "truths" obvious? (Spoiler alert: yes, they are)
In your long text I see two "truths" that you've found:
If you write arrays indices as strings and then reinterpret those strings as numbers for two consecutive permutations, the difference will a multiply of 9
The "graph of slopes" is symmetric
Unfortunately both of these facts are quite obvious and one of them is not even really true.
First fact is true as long the length of the array is less than 10. If it is more than 10 i.e. some indices are "mapped" to 2 characters, it stops being true. And it is obviously true if you know a divisibility rule for 9 (in decimal system): sum of digits should be a multiply of 9. Obviously if both of the numbers have the same digits they have the same reminder module 9 and thus their difference is a multiply of 9. Moreover, if you interpret your string in any system with base more than length of the array, the difference will be a multiply of base - 1 for the same reason. For example, let's use 8-based system (columns are: permutation, permutation index, indices string, indices string converted from 8-based to decimal, difference):
abc 0 012 10
acb 1 021 17 7
bac 2 102 66 49
bca 3 120 80 14
cab 4 201 129 49
cba 5 210 136 7
If you always use based of the system that is greater than the length of the array, this fact will be true (but you might need to come up with new digits)
The second statement is obvious as well and is direct consequences of how "lexicographic order" is defined. For every index i, if I sum indices array of the first i-th permutation and the last i-th permutation, the sum will always be the same: array with all values equal to the length of the array. Example:
1. abc 012 - cba 210 => 012 + 210 = 222
2. acb 021 - cab 201 => 021 + 201 = 222
3. bac 102 - bca 120 => 102 + 120 = 222
This is easy to see if you consider permutations of an array of negative indices i.e. [-N, -(N-1), ..., -1, 0]. Obviously i-th permutation from the start of this array is the same as i-th permutation of the [0, 1, 2, ... N] from the end with just negated signs.
Other questions
- Are there a mathematical relationships or patterns between the indexes as numbers, that is, for example, the set of numbers at graph 1, graph 2 or graph 3, derived from the input of any four values, for example
Yes, there are. Actually this is exactly the reason why the answer you linked in your question Permutations without recursive function call works in the first place. But I doubt there is an algorithm significantly more efficient than the one provided in that answer. Effectively that answer tries to convert the position of the requested permutation into a value in a variable-base numerical system with bases ranging from 1 to the length of the array. (For a more widespread example of a variable-base numerical system consider how you convert milliseconds into days-hours-minutes-seconds-milliseconds. You effectively use numerical system with bases 1000-60-60-24-unlimited. So when you see 12345 days 8 hours 58 minutes 15 seconds 246 milliseconds you convert it to milliseconds as ((((12345 * 24 + 8) * 60) + 58 * 60) + 15) * 1000 + 246 i.e. you treat that notation as 12345 (no base/unlimited) days 8 (24-base) hours 58 (60 base) minutes 15 (60 base) seconds 246 (1000-base) milliseconds).
With permutations there are two different tasks that you might need to do:
Generate
i-thpermutation. The algorithm you linked in the SO answer is reasonably efficient. And I doubt there is anything much betterGenerate all permutations or a stream of permutations or next permutation for given one. This seems to be the one you are trying to do with your code. In this case simple algorithm that analyses given permutation, finds the first place where the permutations is not sorted, and does the switch + sorting is reasonably efficient (this is what procrastinator seems to implement but I didn't look into details). And again I doubt there is anything much better. On of major obstacles why numeric-based algorithm will not be more efficient is because for it to work in general case (i.e. length >= 10), you'll need to do divisions using long arithmetic in large bases and those operations are not O(1) anymore.
Update (answer to comment)
What I claim is that there is no way to calculate the sequence of numbers that would be more efficient than a direct calculation of the sequence of permutations.
I disagree as to that proposition. Can you show and prove as to that claim?
No, I don't even know how to state this claim in a formal way (how to define the class of algorithms that doesn't calculate that sequence of numbers?). Still I have some evidence to support this point.
First of all, you are probably not the smartest man in the known Universe, and this is relatively old and well known topic. Thus chances that you have discovered an algorithm that is much faster than existing ones are low. And the fact that nobody uses this techique is an evidence against you.
Another point is less arbitrary: the algorithm I suggested at #2 for generating all permutations in sequence is actually reasonably efficient and thus it will be hard to beat.
Consider some step to find next permutation. First you need to find the first position from the end where the order is not descending. Assume it would be k. It would take k comparisions to find it. Then you need to do one swap and sort. But if you are a bit smart, you might notice that "sort" here might be done much faster because the list is already sorted (but in reverse order). Thus sort here is just reverse with finding place for the k-th element. And taking into account that array is sorted, you can use binary search with O(log(k)) complexity. So you need to move k+1 elements in memory and less than k comparisions. Here is some code:
// generates array of all permutatations of array of integers [0, 1, .., n-1]functionpermutations(n) {
// custom version that relies on a fact that all values are unique i.e. there will be no equalityvar binarySearch = function (tgt, arr, start, end) {
// on small ranges direct loop might be more efficient than actual binary searchvarSMALL_THRESHOLD = 5;
if (start - end < SMALL_THRESHOLD) {
for (var i = start; i <= end; i++) {
if (arr[i] > tgt)
return i;
}
thrownewError("Impossible");
}
else {
var left = start;
var right = end;
while (left < right) {
var middle = (left + right) >> 1; //safe /2var middleV = arr[middle];
if (middleV < tgt) {
left = middle + 1;
}
else {
right = middle;
}
}
return left;
}
};
var state = [];
var allPerms = [];
var i, swapPos, swapTgtPos, half, tmp;
for (i = 0; i < n; i++)
state [i] = i
//console.log(JSON.stringify(state));
allPerms.push(state.slice()); // enfroce copyif (n > 1) {
while (true) {
for (swapPos = n - 2; swapPos >= 0; swapPos--) {
if (state[swapPos] < state[swapPos + 1])
break;
}
if (swapPos < 0) // we reached the endbreak;
// reverse end of the array
half = (n - swapPos) >> 1; // safe /2for (i = 1; i < half + 1; i++) {
//swap [swapPos + i] <-> [n - i]
tmp = state[n - i];
state[n - i] = state[swapPos + i];
state[swapPos + i] = tmp;
}
// do the final swap
swapTgtPos = binarySearch(state[swapPos], state, swapPos + 1, n - 1);
tmp = state[swapTgtPos];
state[swapTgtPos] = state[swapPos];
state[swapPos] = tmp;
//console.log(JSON.stringify(state));
allPerms.push(state.slice()); // enfroce copy
}
}
//console.log("n = " + n + " count = " + allPerms.length);return allPerms;
}
Now imagine that you do the same with your number-based approach and for a moment assume that you can calculate the number to add for each step instantly. So how much time do you use now? As you have to use long arithmetics and we known that highest digit that will be changed by your addition is k-th, you'll need to perform at least k additions and k comparisions for overflow. And of course you'll still have to do at least k writes to the memory. So to be more efficient than described above "usual" algorithm, you need a way to calculate a k-digits long number (the one you will add) in a time that takes less than to perform a binary search in array of size k. This sounds to me as a quite tough job. For example, multiplication of 9 (or rather N-1) by corresponding coefficient alone will probably take more time using long arithmetics.
So what other chances do you have? Don't use long arithmetics at all. In this case, the first obvious argument is that mathematically it makes little sense to compare alrgorithms performance on small N (and this is why Big-O notation is used for algorithms complexity). Still it might make sense to fight for performance of a "small" from the pure mathematics' point of view but "big" for real world cases in range up to permutation of array of 20 elements that still would fit into a long (64-bit) integer. So what you can gain by not using long arithmetics? Well your additions and multiplications will take only one CPU instruction. But then you'll have to use division to split your number back to digits and it will take N divisions and N checks (i.e. comparisions) on each step. And N is always greater than k, often much more. So this also doesn't look like a great avenue for performance improvements.
To sum up: suggested alogrithm is efficient and any arithmetics-based algorithm will probably less efficient in arithmetics part.
Solution 2:
When solving problems having many different tools in your tool box helps. A tool that applies to this problem is The On-Line Encyclopedia of Integer Sequences® (OEIS®).
As noted in the question is the sequence
9,81,18,81,9,702,9,171,27,72,18,693,18,72,27,171,9,702,9,81,18,81,9
which can be generated by taking the lexicographic permutations of 1,2,3,4 and converting them to numbers
1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124,3142,3214,3241,3412,3421,4123,4132,4213,4231,4312,4321then subtracting a permutation from its predecessor, e.g.
1243-1234=91324-1243=811342-1324=18...Now the OP notes all of the difference values are divisible by 9, so dividing by 9 gives
1, 9, 2, 9, 1, 78, 1, 19, 3, 8, 2, 77, 2, 8, 3, 19, 1, 78, 1, 9, 2, 9, 1
and with a OEIS search gives
A217626 - ... first differences of permutations of 123...m, divided by 9 (with m sufficiently large, m! > n).
With regards to the OP question
the mathematical formula to derive the precise number which needs to be added, or multiplied by 9, to the current whole number representation of indexes of the current permutation to get the next whole number representation of the indexes of the next lexicographic permutation.
In the links section is
R. J. Cano, Additional information about this sequence.
and clicking on Additional information about this sequence.
brings up a page that talks about the symmetry of the sequence
{ 1, 9, 2, 9, 1, 78, 1, 19, 3, 8, 2, 77, 2, 8, 3, 19, 1, 78, 1, 9, 2, 9, 1 }
These elements are the first 4! terms of this sequence. The symmetry center for this case (permutations for N=4) is the 12th term, because by deleting it and the zero starting this sequence, only left an even amount of terms which are repeated once according to their offsets relative to the symmetry center, as shown in the following transformations:
0) { 0, 1, 9, 2, 9, 1, 78, 1, 19, 3, 8, 2, 77, 2, 8, 3, 19, 1, 78, 1, 9, 2, 9, 1 }; Delete the zero,
1) { 1, 9, 2, 9, 1, 78, 1, 19, 3, 8, 2, 77, 2, 8, 3, 19, 1, 78, 1, 9, 2, 9, 1}; Split apart in three pieces one of them the symmetry center,
2) { 1, 9, 2, 9, 1, 78, 1, 19, 3, 8, 2 }; { 77 }; { 2, 8, 3, 19, 1, 78, 1, 9, 2, 9, 1 }; Delete the symmetry center,
3) { 1, 9, 2, 9, 1, 78, 1, 19, 3, 8, 2 }; { 2, 8, 3, 19, 1, 78, 1, 9, 2, 9, 1 }; Reflect one of the pieces,
4) { 1, 9, 2, 9, 1, 78, 1, 19, 3, 8, 2 }; { 1, 9, 2, 9, 1, 78, 1, 19, 3, 8, 2 }; A new kind of center becomes evident after this step.
Since all the possible permutation sets have all in common some terms from this sequence, we may expect find again these "centers" when developing another cases.
With regards to an code/algorithm there is another reference in the links section
R. J. Cano, Template for a base-independent sequencer in C.
/*
* ##########################################
* # Base independent sequencer for A217626 #
* ##########################################
*
* This program is free software.
* Written by R. J. Cano (remy at ula.ve, Or reemmmyyyy at gmail.com)
* On Jan 9 2014, for educational purposes and released under
* the terms of the General Public License 3.0 (GNU-GPL 3.0);
*
* There is NO warranty not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* Note: For a large set of terms (>10!-1) the present program might be prone to data type overflows.
*
*/#include<stdio.h>#include<stdlib.h>long _base= 10;
long _showOffset= 1;
/** Standard output field width. An aid for comparisons using MD5 checksums. **/long _normWidth= 13;
/** Set this to 0 for print everything in a single line. **/long _onePerLine= 1;
/** 0 for the vector representation, 1 for the integer representation **/long _objectToShow= 1;
longpermute(long*, long*, long);
longvec2polyEval(long*, long, long);
intmain(int argc, char *argv[]){
long v1[100],v2[100],v3[100],u[100],n,k,l,offset=0;
_showOffset*= _onePerLine;
/* The size of the output (n!-1 items) is no longer read from the standard input.
scanf("%li",&n); -- Does stop silently, therefore it is avoided. */
n= strtol(argv[1], NULL, _base); /* Direct conversion from the command line parameter(s) */for(k=0; k<100; k++) {
v1[k]= (k<n)*(k);
v2[k]= v1[k];
v3[k]= 0;
}
while(permute(v2,u,n)) {
for(k=0;k<n-1;k++) {
v3[k+1]=0;
for(l=k+1;l<n;l++) {
v3[k+1]+=(u[l]-v2[l]);
}
}
if (_showOffset) printf("%li ", ++offset);
if (!_onePerLine) printf(",");
if (!_objectToShow) {
for(k=0;k+n<_normWidth;k++) { printf(",0"); }
for(k=0;k<n;k++) { printf(",%li",v3[k]); }
printf(";");
} else {
printf("%li", vec2polyEval(v3,_base,n));
}
if (_onePerLine) printf("\n");
}
if (!_onePerLine) printf("\n");
return EXIT_SUCCESS;
}
longpermute(long *data, long *previous, long Size){
long tau, rho=Size-1, phi=Size-1;
for (tau=0;tau<Size;tau++) previous[tau]= data[tau];
while((rho > 0)&&(data[rho]<= data[rho-1])) rho--;
rho--;
if(rho<0) return0;
while((phi > rho)&&(data[phi]<=data[rho])) phi--;
tau= data[rho];
data[rho]= data[phi];
data[phi]= tau;
Size--;
rho++;
while(Size>rho) {
tau= data[Size];
data[Size]= data[rho];
data[rho]= tau;
Size--;
rho++;
}
return1;
}
longvec2polyEval(long* v, long B, long m){
long ans=0, pow=1, k;
for(k=m-1;k>=0;k--) {
ans+= v[k]*pow;
pow*= B;
}
return ans;
}
Example
To run the C code I used Visual Studio Community 2015 which is free, and built as a Win32 console project.
C:\Users\Eric\Documents\Visual Studio 2015\Projects\OEIS_A217626\Debug>OEIS_A217626 1C:\Users\Eric\Documents\Visual Studio 2015\Projects\OEIS_A217626\Debug>OEIS_A217626 2
1 1
C:\Users\Eric\Documents\Visual Studio 2015\Projects\OEIS_A217626\Debug>OEIS_A217626 3
1 1
2 9
3 2
4 9
5 1
C:\Users\Eric\Documents\Visual Studio 2015\Projects\OEIS_A217626\Debug>OEIS_A217626 4
1 1
2 9
3 2
4 9
5 1
6 78
7 1
8 19
9 3
10 8
11 2
12 77
13 2
14 8
15 3
16 19
17 1
18 78
19 1
20 9
21 2
22 9
23 1
C:\Users\Eric\Documents\Visual Studio 2015\Projects\OEIS_A217626\Debug>OEIS_A217626 5
1 1
2 9
3 2
4 9
5 1
6 78
7 1
8 19
9 3
10 8
11 2
12 77
13 2
14 8
15 3
16 19
17 1
18 78
19 1
20 9
21 2
22 9
23 1
24 657
25 1
26 9
27 2
28 9
29 1
30 178
31 1
32 29
33 4
34 7
35 3
36 66
37 2
38 18
39 4
40 18
41 2
42 67
43 1
44 19
45 3
46 8
47 2
48 646
49 1
50 19
51 3
52 8
53 2
54 67
55 1
56 29
57 4
58 7
59 3
60 176
61 3
62 7
63 4
64 29
65 1
66 67
67 2
68 8
69 3
70 19
71 1
72 646
73 2
74 8
75 3
76 19
77 1
78 67
79 2
80 18
81 4
82 18
83 2
84 66
85 3
86 7
87 4
88 29
89 1
90 178
91 1
92 9
93 2
94 9
95 1
96 657
97 1
98 9
99 2
100 9
101 1
102 78
103 1
104 19
105 3
106 8
107 2
108 77
109 2
110 8
111 3
112 19
113 1
114 78
115 1
116 9
117 2
118 9
119 1
A test with 10, which can bring down some algorithms works nicely.
C:\Users\Eric\Documents\Visual Studio 2015\Projects\OEIS_A217626\Debug>OEIS_A217626 10
1 1
2 9
3 2
4 9
5 1
6 78
7 1
8 19
9 3
10 8
...
3628790 8
3628791 3
3628792 19
3628793 1
3628794 78
3628795 1
3628796 9
3628797 2
3628798 9
3628799 1
Note: The number of answers is X!-1 and 10! = 3628800 There is one less than the factorial because this is calculating the differences.
I did not convert this to JavaScript because your efficiency at JavaScript is probably better than mine at present. Currently I am focused on Prolog and F#.
Supplement
If you are visiting this question to learn about enumerating permutations on a computer then two particular papers you should read are
Permutation Generation Methods by Robert Sedgewick
"The Art Of Computer Programming" A draft of section 7.2.1.2 Generating all permutations by Donald E. Knuth.
and the book
Enumerative Combinatorics by Richard P. Stanley
Solution 3:
Lack of skills in maths and english makes it hard for me to elaborate on such a question :-| Though I wanted to play with permutations and I did something not so off-topic after all. See TL;DR at https://stackoverflow.com/a/43302308/1636522, I have the same feeling and I'll try to demonstrate the validity of my algorithm later, I need a little time to think of it.
var a = "aceg".split("");
do {
console.log(a.join(""));
} while (a = next(a));
functionnext (a) {
var i, c, head, next;
var b = a.slice();
var n = b.length;
for (i = 1; i < n; i++) {
if (b[n - i] > b[n - (i + 1)]) {
head = n - (i + 1);
next = n - i;
for (i = next + 1; i < n; i++) {
if (b[i] < b[next] && b[i] > b[head]) {
next = i;
}
}
c = b[head];
b[head] = b[next];
b[next] = c;
return b.slice(0, head + 1).concat(
b.slice(head + 1).sort()
);
}
}
}
Post a Comment for "How To Improve Efficiency Of Algorithm Which Generates Next Lexicographic Permutation?"