Menu
It must be noted here that I performed the mathematics by hand on paper to derive the foregoing proofs. I am not sure if the proofs would have become apparent by solely using the medium of the modern computer.
The definition of "efficiency" as used below meaning completing a discrete portion of the algorithm, or the entire algorithm in the least amount of time. Both as to mathematically and, programmatically, or computationally.
While further examining procedures for generating the next lexicographic permutation from the original set or current permutation, following re-reading the Answer by @chqrlie at Permutations without recursive function call, I began the inquiry by writing the indexes on paper in an attempt to observe any mathematical relationships between the indexes that could be utilized to perform the specific task.
I discovered several interesting truths, the proofs thereof demonstrated below.
When we write, for example, the values
a,b,c
or
abc
or, instead write the indexes representing the values
0,1,2
or
012
Since we know, given a set
abc
that we can generate the next lexicographic permutation by swapping the last two values or indexes of the set
acb
or
021
we can ignore the values, which could be any type of data, and concentrate on using the indexes for our examinations, as discrete numbers are more suited for correlating possible relationships than a possibly infinite amount of diversified values.
Therefore, with the second lexicographic index of the original set
abc
we can denote the values of the indexes as numbers, and observe
0,2,1
or
021
The first indexes being
012
the second being
021
Since we know the .length of the original set is 3, if we remember the .length of the original set of values, we can remove the starting
0
where to reduce the indexes to the number
12
and
21
respectively. Where the 0 can be referenced as the index from original set to get the value at index 0 when the resulting set of the next operation is less than the original set.
When we attempt to graph potential relationships between 12 and 21, we find that
21 - 12 = 9
When we continue, we find that the next lexicographic indexes are
102
subtracting the previous indexes
102 - 21 = 81
where 102 is the next lexicographic permutation, represented as the values
bac
which provides us with the common relationship between the indexes being the number nine, represented numerically as
9
This relationship is evident and reproducible for an infinite set of input values represented as numbers. We can graphs of the relationships, which, depending on the perspective of the observer, can be viewed as two slopes, with an inverted apex offset when beginning the graph from the first value of the set of resulting permutations
// graph 1
0,9,81
// graph 2
abc 012 0
acb 021 1 9
bac 102 2 81
bca 120 3 18
cab 201 4 81
cba 210 5 9
/\/\
/ \
We can observe here that the number on the graph at the inclination slope is identical to the number at the correpsonding declination slope, following the inversion of the number of the divided total number of possible permutations divided by half, where for example, for a total of six permutation, we subtract one, leaving remainder of five, remembering that we still need the odd set of indexes, we use the number at the inverted apex as a pivot, leaving four indexes, which we denote as inclination and declination slopes, respectively.
We observer here that the numbers on the graph of the declination slope are identical to the correponding adjacent angle of the inclination slope at the same y coordinate.
Thus,below I demonstrate the proof that an infinite set of permutations given an infinite input set can be calculated, generated, filtered, derived by utilizing addition or multiplication of the number nine
9
by matching numbers which include only the number of the index of an input number, without duplicate in the set.
Further, I demonstrate the proof that need only the indexes as numbers on inclination slope, or the total amount of possible permutations divided by two plus one, are needed to derive the total number of permutations of a given input.
As stressed at the preface of this post, this calculations could perhaps not have been possible without many hours of doing the math by hand on paper. The media screen simple does not provide the same medium as composing the characters one by one on paper; with the ability to view the paper from various physical dimensions.
The expression of the algorithm using a coding language is another task unto itself.
The following is a progression of the discoveries, proofs and expressions thereof implemented using the "JavaScript" programming language. The first version has a RegExp that is not accurate as to the expected result, as pointed out by @Tushar, with corrected RegExp, though incorrect RegExp returns same result.
Given input as array
var arr = ["a", "b", "c", "d"];
// version 1
function getNextLexicographicPermutation(arr) {
var len = arr.length;
var idx = arr.map(function(_, index) {
return index
});
var re = new RegExp("[" + len + "-9]|(.)(?!=\\1)");
var n = Math.pow(10, len - 1);
var p = 9;
var last = Number(idx.slice().reverse().join(""));
var res = [idx];
var curr = Number(res[res.length - 1].join(""));
while (curr < last) {
for (var prev = curr, next, k; prev <= last; prev += p) {
if ((re.test(prev))) {
k = String(prev);
if (k.length >= len - 1) { // && Math.max.apply(Math, j) < len
next = [];
for (var i = 0; i < k.length; i++) {
if (next.indexOf(Number(k[i])) == -1
&& idx.indexOf(Number(k[i])) !== -1) {
next.push(Number(k[i]))
}
}
if (prev < n && next.length === len - 1
|| next.length === len && prev > curr) {
res[res.length] = next.length < len
? [0].concat.apply([0], next)
: next;
}
}
}
curr = prev;
}
};
return res.map(function(value) {
return value.map(function(index) {
return arr[index]
})
})
}
getNextLexicographicPermutation(arr);
The graph for numerical difference between the numbers as indexes for the array arr will be
// graph 3
// reflecting input `abcd`
[9,81,18,81,9,702,9,171,27,72,18,693,18,72,27,171,9,702,9,81,18,81,9]
// version 2.0 without using `RegExp`
function getNextLexicographicPermutation(arr) {
var len = arr.length;
var idx = arr.map(function(_, index) {
return index
});
var n = Math.pow(10, len - 1);
var p = 9;
var last = Number(idx.slice().reverse().join(""));
var res = [];
var curr = Number(idx.join(""));
var prev, k, next;
while (curr <= last) {
prev = curr;
k = String(prev).split("").map(Number);
if (k.every(function(v) {
return idx.indexOf(v) !== -1
}) && k.length >= len - 1) {
next = [];
for (var i = 0; i < k.length; i++) {
if (next.indexOf(Number(k[i])) == -1
&& idx.indexOf(Number(k[i])) !== -1) {
next.push(Number(k[i]))
}
}
if (prev < n && next.length === len - 1
|| prev > n && next.length === len)) {
res[res.length] = next.length < len
? [0].concat.apply([0], next)
: next;
}
}
prev += p;
curr = prev;
};
return res.map(function(item) {
return item.map(function(v) {
return arr[v]
})
})
}
getNextLexicographicPermutation(arr)
The efficiency of the second version was greatly improved over the first version by substituting bitmask for RegExp by Answer of @lleaff at Most efficient method to check for range of numbers within number without duplicates.
The relevant profiles generated by DevTools between the RegExp version and bitmask version should be reprodicible at chromium browser, however due to neglecting commenting the exact tests performed, am not able to precisely reproduce the numbers and times posted without devoting more time to verifying the numbers posted at previous Question. Cannot remember precisely, though browser tab may have crashed when .length of input set was ten. What was important was that the bitmask test version was more efficient than RegExp test version.
// version 2.1, substituting bitmask for `RegExp`
function getNextLexicographicPermutation(arr) {
function checkDigits(min, max, n) {
var digits = 0;
while (n) {
d = (n % 10);
n = n / 10 >> 0;
if (d < min || d > max || (digits & (1 << d)))
return false;
else
digits |= 1 << d;
}
return true;
}
var len = arr.length,
idx = arr.map(function(_, index) {
return index
}),
p = 9,
min = 0,
max = len - 1,
last = Number(idx.slice().reverse().join("")),
res = [],
curr = Number(idx.join("")),
next;
while (curr < last) {
next = (curr += p);
if (checkDigits(min, max, next)) res[res.length] = next;
curr = next;
};
return res.map(function(item) {
var item = String(item).split("").map(Number);
item = item.length < arr.length ? [0].concat(item) : item;
return item.map(function(index) {
return arr[index]
}).filter(Boolean)
})
}
getNextLexicographicPermutation(arr);
The notes and process took the better part of a year, over a year ago, to show and prove. Have mainly simply thought how to get indexes for either side of slope simultaneously, using only inclination slope indexes, rather than coding the algorithm therefore.
The bulk of the math was in trying to derive a further correlation between the adjacent multiples of the number nine, for the ability to calaculate the exact next multiple of the number nine
9
for incrementing a number by nine then filtering duplicate values from the resulting number. I have not yet been able to decipher the inter-relationships between the adjacent multiples of nine on the inclination slope to the degree that multiplication or division could be substituted for addition and exclusion.
Decided to finally create proof of concept for the proposition of generating an infinite number of permutations from an infinite input set, using only the inclination slope, or only the indexes as numbers, of the first half of possible permutations plus one.
// version 3, generate second half of permutations using indexes of first
// half of permutations
function getNextLexicographicPermutation(arr) {
for (var l = 1, i = k = arr.length; l < i ; k *= l++);
function checkDigits(min, max, n) {
var digits = 0;
while (n) {
d = (n % 10);
n = n / 10 >> 0;
if (d < min || d > max || (digits & (1 << d)))
return false;
else
digits |= 1 << d;
}
return true;
}
var len = arr.length
, idx = arr.map(function(_, index) {
return index
})
, p = 9
, min = 0
, max = len - 1
, last = Number(idx.slice().reverse().join(""))
, curr = Number(idx.join(""))
, res = []
, diff = []
, result = []
, next;
while (res.length < (k / 2) + 1) {
next = (curr += p);
if (checkDigits(min, max, next)) res[res.length] = next;
curr = next;
};
for (var i = 0; i < res.length; i++) {
var item = res[i];
item = String(item).split("").map(Number);
item = (item.length < arr.length ? [0].concat(item) : item)
.map(function(index) {
return arr[index]
}).filter(Boolean);
result.push(item)
}
res.reduce(function(a, b) {
diff.push(b - a);
return b
});
for (var i = 0, curr = res[res.length - 1], n = diff.length - 2
; result.length < k; i++, n--) {
curr = curr + diff[n];
result.push(
String(curr).split("")
.map(function(index) {
return arr[index]
})
);
}
return result;
}
getNextLexicographicPermutation(arr);
Another eventual step in development of the algorithm will be given an arbitrary .length input, to be able to calculate the indexes, and thus the values of the nth permutation of the set mathematically; by using only a single formula of multiplication, division, algebra, trigonotetry or calculus.
Please include reproducible benchmarks within Answer. The reason being is that cannot remember exactly how I derive the numbers for Profiles at DevTools, though if remember correctly used console.time(), console.timeEnd() and console.profile() at beginning and end of respective portions where used. Backup your experiments; you never know if or when a hard drive or OS will crash. You can generally retrieve the data from the disk, though at cost of time and effort to do so. Save your tests in same fashion you save versions of algorithms as well, for ability to reproduce yourself and for others to reproduce. The full gamut of the original tests are lost.
The surviving remnants of the test for how many permutations could be derived before browser tab crashed are only comments retrieved from a different OS
// 362880 876543210 876543219
var arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i"];
where if recollect accurately, when "j" was added to the array, the active tab at chromium crashed. The first number is the total amount of permutations for the set "a" through "i"; the next two number are probably, though not certain, the results of two tests for one of the versions before version 3, which composed today.
That is another reason for now posting the above disclosure here at stackoverflow.com, to preserve the principals of the algorithm and work on the code done so far, less some catastrophe destroy all of the original notes and work; for example, being awake for several days in a row trying to interpret patterns and relationships between numbers; neglecting to document all of the specific test patterns tried attempting to port the algorithm to code at comments within code; or as @JaromandaX described the circumstance "PEBCAK".
Fresh eyes can probably see the algorithm from a different perspective as to efficiency.
We can reproduce a graph of the results from some of the preserved code versions above, for example using console.time(), console.timeEnd(), performance.now() or other appropriate tests involving time to complete the function, which can be reproduced.
// console.time("version N");
// getNextLexicographicPermutation(arr);
// console.timeEnd("version N");
var tests = [];
for (var i = 0; i < 10000; i++) {
var from = window.performance.now();
getNextLexicographicPermutation(arr);
tests.push(window.performance.now() - from);
}
for (var i = 0, k = 0; i < tests.length; i++) {
k += tests[i];
}
var avg = k/tests.length;
// version 1 `avg`: 0.2989265000001993
// version 2.0 `avg`: 0.8271295000007376
// version 2.1 `avg`: 0.17173000000003666
// version 3 `avg`: 0.12989749999987543
As a footnote, I will mention that I used the principals of the algorithm to derive the expected results at Fastest way to generate all binary strings of size n into a boolean array?, where again, the number nine appeared as a key number within the inclination slope, and the matching angle of declination is also observable. Though did not perform futher tests and automation of the specific form of input and result described at that Question. The Answer was a proof of concept as to the viability of the approach of ignoring the values and using only a wave-like incrementing pattern applied to a single number initial number, zero, to derive infinite permutations of a set.
Questions:
How can the algorithm be improved as to efficiency; both computationally and mathematically?
Can we create the indexes for both inclination and declination slope at the same time; rather than determining the declination slope after the inclination slope has been calculated?
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
abcd
or
["a", "b", "c", "d"]
that the author has not yet to recognize; which could be used to further reduce the number of computations currently implemented to derive results?
512
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-th permutation. The algorithm you linked in the SO answer is reasonably efficient. And I doubt there is anything much better
Generate 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]
function permutations(n) {
// custom version that relies on a fact that all values are unique i.e. there will be no equality
var binarySearch = function (tgt, arr, start, end) {
// on small ranges direct loop might be more efficient than actual binary search
var SMALL_THRESHOLD = 5;
if (start - end < SMALL_THRESHOLD) {
for (var i = start; i <= end; i++) {
if (arr[i] > tgt)
return i;
}
throw new Error("Impossible");
}
else {
var left = start;
var right = end;
while (left < right) {
var middle = (left + right) >> 1; //safe /2
var 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 copy
if (n > 1) {
while (true) {
for (swapPos = n - 2; swapPos >= 0; swapPos--) {
if (state[swapPos] < state[swapPos + 1])
break;
}
if (swapPos < 0) // we reached the end
break;
// reverse end of the array
half = (n - swapPos) >> 1; // safe /2
for (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.
195
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,4321
then subtracting a permutation from its predecessor, e.g.
1243 - 1234 = 9
1324 - 1243 = 81
1342 - 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;
long permute(long*, long*, long);
long vec2polyEval(long*, long, long);
int main(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;
}
long permute(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) return 0;
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++;
}
return 1;
}
long vec2polyEval(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;
}
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 1
C:\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#.
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
37
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
