Permutations to the nines
This question is based on an unresolved inquiry which began at Permutations without recursive function call and was followed up at How to improve efficiency of algorithm which generates next lexicographic permutation? (TL;DR), after finding help removing duplicate numbers at Most efficient method to check for range of numbers within number without duplicates, where after performing arithmetic by hand found that for an array having length less than or equal to 9, if we ignore the value held at each index of the initial array and instead convert the indexes to a whole number, the next lexicographic permutation can be determined by adding 9 to the current index as number until a whole number, e.g., [1,2,3] // 123 1-based index or 23 0-based index is reached that satisfies two the conditions
e.g., 123+9=132 // "abc" -> "acb" 132-9=123 // "acb" -> "abc"; the graph for "abcd" is
[9,81,18,81,9,702,9,171,27,72,18,693,18,72,27,171,9,702,9,81,18,81,9]
which does not appear to be linear.
As the linked answers disclose, adding 9 to a whole number is not the most efficient method of determining the next lexicographic permutation, and what found independently by hand has been found by others, consider OEIS A217626
A217626 First differences of A215940, or first differences of
permutations of (0,1,2,...,m-1) reading them as decimal numbers,
divided by 9 (with 10>=m, and m! > n).
1, 9, 2, 9, 1, 78, 1, 19, 3, 8, 2, 77, 2, 8, 3, 19, 1, 78, 1, 9, 2, 9,
1, 657, 1, 9, 2, 9, 1, 178, 1, 29, 4, 7, 3, 66, 2, 18, 4, 18, 2, 67,
1, 19, 3, 8, 2, 646, 1, 19, 3, 8, 2, 67, 1, 29, 4, 7, 3, 176, 3, 7, 4,
29, 1, 67, 2, 8, 3, 19, 1, 646, 2, 8, 3, 19, 1
Also of interest is that the graph of the specific multiples of 9 to derive all lexicographic permutations of a set can be found by computing only half 1/2 of the total permutations +1, as the declination slope is identical to the inclination slope of multiples of 9, for example, given an input of the string "abc" or array ["a","b","c"], we only need to reach the inverted peak of the graph, that is bca 120 3 18, where the previously calculated values can be reversed and added to the current whole number, 120, to generate the remainder of the lexicographic permutations
abc 012 0
acb 021 1 9
bac 102 2 81
bca 120 3 18
cab 201 4 81
cba 210 5 9
/\/\
/ \
Errata
This challenge is not to determine the most efficient algorithm to calculate permutation 9!, as, again, adding 9 to a whole number to reach that goal can be outperformed by swapping values or other method, as demonstrated at the accepted at the first SO link above.
This challenge is to derive the most efficient method of determining the next lexicographic permutation by calculating the next multiple of 9 that meets the above listed criteria, preferably directly using math, if possible.
The reason am posting this question here and now is because was reminded by the graph of the peaks (particularly the third item) in this question Different combinations possible
Just to give a visual example, they are the following:
/\ /\ /\/\
/\/ \ / \/\ / \
that in spite of performing various calculations using the index of the !n within the resulting array of permutations, e.g.,
var n = N = 1234;
var res = [9,81,18,81,9,702,9,171,27,72,18,693,18,72,27,171,9,702,9,81,18,81,9].map((x)=>n=n+x);
// try to determine the rate of growth
var j = res.map((x)=>x/N);
console.log(res, j);
var tryStuff = 1234*(4321/1234);
console.log(tryStuff, (4321/1234));
am still vexed by and have not been able to independently determine the mathematical formula to derive the next lexicographic permutation directly without adding 9 multiple times to reach the required number; or if that is even mathematically possible for any input set from 2! through 9!. That is, this code
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 = [curr],
diff = [],
result = [],
next, times = 0;
while (res.length < (k / 2) + 1) {
++times;
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, diff, res, times];
}
var arr = ["a", "b", "c", "d"];
console.log(getNextLexicographicPermutation(arr));
which generates the second half-1 of the permutations from the first half+1 of the permutations checks if the next whole number meets the necessary conditions 210 times for an input array of ["a","b","c","d"] which has a resulting .length of 24. Ideally, we want to generate 24 lexicographic permutations using only 12 or 13 checks; or no checks at all, by determining the irrational number or other mathematical algorithm which will directly calculate (or approximate close enough to determine the next multiple of 9) the next whole number which meets the necessary criteria.
Kindly disregard the length of this post, as am trying to include as much information as consider relevant to the inquiry.
Rules
This challenge must use the number 9 (addition, multiplication, division, other mathematical operation) to determine the next lexicographic permutation using the indexes of the current lexicographic permutation converted to a whole number, ideally, in a single operation, else in the least amount of operations necessary to achieve the expected result.
Again, this challenge is not asking how to code the most efficient code which determines the next lexicographic permutation, but what is the most efficient approach is using only the number 9 and math to generate the permutations.
Since we can get the first and last lexicographic permutations by reversing the indexes of the input array, that is not counted as an operation within the program.
Input
An array or sting having .length less than or equal to 9!.
Output
Lexicographically sorted array of permutations of input.
Task
Remaining within the Rules above, determine a mathematical algorithm which directly generates the next lexicographic permutation using only the current indexes of the original input or current permutation. Ideally, directly, without having to add 9 in multiple operations until the listed criteria is met, that is, we want a single algorithm to calculate that we need to add 81 to 132 to get the sum 213 and add 702 to 321 to get the sum 1023 and so forth. Explain the math in the algorithm. Note: The requirement might not be possible. If that is the case, explain why.
