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?
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.