I have an array with a lot of items. For clarification, I will use an array of numbers:
[1, 2, 3, 4, 5, 6, 7, 8]
I also have an array with pair of items which should be distant from each other:
[[1, 3], [6, 8], [2, 5]]
I need to random this array, but ensure that this pair of items will have a distance of arr.length - pairs.length (3 on this case) between them.
On this case, some of the correct orders should be:
[1, 6, 4, 2, 3, 8, 7, 5]
[3, 4, 5, 8, 1, 7, 2, 6]
All pair items have a distance of 3 . I need a function to sort the array but follow this rule.
Can someone help me?
I created an algorithm but it isn't working and the loop is not stopping, even with the last value being valid according to the rules
const arr = [1, 2, 3, 4, 5, 6, 7, 8]
const pairs = [[1, 3], [6, 8], [2, 5]]
function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
const distance = arr.length - pairs.length
const getDistance = (arr, a, b) => {
return Math.abs(arr.indexOf(a) - arr.indexOf(b))
}
const isValid = (arr) => {
for (const pair of pairs){
if (getDistance(arr, pair[0], pair[1]) < distance){
return false
}
}
return true
}
const similars = {}
for (const pair of pairs){
similars[pair[0]] = pair[1]
similars[pair[1]] = pair[0]
}
shuffleArray(arr)
let index = 0;
while (!isValid(arr)){
const item = arr[index]
if (getDistance(arr, item, similars[item]) < distance){
arr.push(item);
arr.splice(index, 1)
}
else {
index
}
console.log(arr)
}
console.log(arr)
CodePudding user response：
OK, this is a complicated one. The approach that I give here will top out somewhere between 20 and 30 pairs.
First, let's discuss conceptually what we want to do when choosing an element.
We'll have a freeValues list of values you can use at this point, a freePairs list of pairs we can use, and an upcoming that says when a particular value graduates from upcoming to available (namely after we've reached the right distance). So the idea is:
if decide to use free:
use a random freeValue
else:
pick a random pair
use one of its values, stick the other in upcoming
update upcoming
Using a random value is straightforward, the challenge is the decision.
But we can record the decisions in a simple string. To take your [1, 6, 4, 2, 3, 8, 7, 5] example above, the decisions were ppfpffff.
For the decisions we need to know how many ways there were of completing our permutation if we choose a free choice vs pair. Then we can make random decisions.
Count of how many ways to do a thing strongly suggests using dynamic programming. But actually we need not just counts, we also need some more information. Still we'll use that.
Dynamic programing comes in two flavors, top down and bottom up. Top down is always easier to write - you just write a recursive function and add caching logic to "memoize" it. So we'll do that.
Now what we will actually do is develop an analysis that looks like:
[count of options, further analysis, state]
Our count is just a count. Our further analysis is just a dictionary mapping choices (free/pair) to its own analysis (or undefined at the very end). Our state will be (countFree, countPairs, toFree) where the counts are just counts of freeValues and freePairs, and toFree is a bitpattern of when the other half of pairs come free. So, for example, if toFree was 5 that would represent a value coming free after this entry, none the entry after, and then another the entry after that.
An important note, the state is the state AFTER we make the choice that gets us there, And not before.
Now let's write code for that analysis.
function analyzePattern (values, pairs) {
let countPairs = pairs.length;
let countFree = values.length - 2 * countPairs;
return _analyzePattern(countFree, countPairs, countPairs, 0, {});
}
function _analyzePattern(countFree, countPairs, minDistance, toFree, cache) {
const key = `${countFree} ${countPairs}, ${toFree}`;
const state = [countFree, countPairs, toFree];
if (! cache[key]) {
if (0 == Math.max(countFree, countPairs)) {
if (toFree) {
cache[key] = [0, undefined, state];
}
else {
cache[key] = [1, undefined, state];
}
}
else {
const answer = {};
let total = 0;
if (toFree % 2) {
// We will be adding a free after this.
// Analyze using a free value here.
let result = _analyzePattern(countFree, countPairs, minDistance, toFree>>1, cache);
let countUseFree = result[0] * countFree;
total = countUseFree;
answer['free'] = [countUseFree, result[1], result[2]];
// Analyze using the first of a pair here.
if (countPairs) {
// Mark that there is an upcoming value to free.
toFree = 2**minDistance;
result = _analyzePattern(countFree 1, countPairs-1, minDistance, toFree>>1, cache);
let countUsePair = result[0] * 2 * countPairs;
total = countUsePair;
answer['pair'] = [countUsePair, result[1], result[2]];
}
}
else {
// We will not be adding a free after this.
if (countFree) {
let result = _analyzePattern(countFree-1, countPairs, minDistance, toFree>>1, cache);
let countUseFree = result[0] * countFree;
total = countUseFree;
answer['free'] = [countUseFree, result[1], result[2]];
}
// Analyze using the first of a pair here.
if (countPairs) {
// Mark that there is an upcoming value to free.
toFree = 2**minDistance;
let result = _analyzePattern(countFree, countPairs-1, minDistance, toFree>>1, cache);
let countUsePair = result[0] * 2 * countPairs;
total = countUsePair;
answer['pair'] = [countUsePair, result[1], result[2]];
}
}
cache[key] = [total, answer, state];
}
}
return cache[key];
}
That will produce our analysis. The next tricky bit is turning the analysis into a random pattern of f's and p's making each permutation equally likely. Note that we have to be careful to use the previous state to make the right random choices.
function randomPattern (analysis, state) {
if (!analysis) {
return '';
}
if (! state) {
state = analysis[2];
}
const total = analysis[0];
const remaining = analysis[1];
const nextState = analysis[2];
if (remaining) {
if (remaining['free']) {
const odds = remaining['free'][0] * state[0] / total;
if (Math.random() < odds) {
return 'f' randomPattern(remaining['free'], state);
}
else {
return 'p' randomPattern(remaining['pair'], state);
}
}
else {
return 'p' randomPattern(remaining['pair'], state);
}
}
else {
return '';
}
}
And now we can finish.
function randomPermutation(values, pairs) {
let inPairs = {};
for (p of pairs) {
inPairs[p[0]] = 1;
inPairs[p[1]] = 1;
}
let freeValues = [];
for (v of values) {
if (! inPairs[v]) {
freeValues.push(v);
}
}
let freePairs = Array.from(pairs);
let distance = pairs.length;
let upcoming = {};
const pattern = randomPattern(analyzePattern(values, pairs));
let answer = []
for (c of pattern) {
if (c == 'f') {
let i = Math.floor(freeValues.length * Math.random());
let tmp = freeValues[i];
freeValues[i] = freeValues[freeValues.length-1];
freeValues[freeValues.length-1] = tmp;
answer.push(freeValues.pop())
}
else {
let i = Math.floor(freePairs.length * Math.random());
let tmp = freePairs[i];
freePairs[i] = freePairs[freePairs.length-1];
freePairs[freePairs.length-1] = tmp;
let pair = freePairs.pop();
if (0.5 < Math.random()) {
answer.push(pair[0]);
upcoming[pair[1]] = distance;
}
else {
answer.push(pair[1]);
upcoming[pair[0]] = distance;
}
}
// Now adjust upcoming.
nextUpcoming = {};
for (const [key, value] of Object.entries(upcoming)) {
if (value <= 1) {
freeValues.push(key-0);
}
else {
nextUpcoming[key] = value-1;
}
}
upcoming = nextUpcoming;
}
return answer;
}
And some test code to try it.
const values = [1, 2, 3, 4, 5, 6, 7, 8];
const pairs = [[1, 3], [6, 8], [2, 5]];
for (let i = 0; i < 10; i ) {
console.log(randomPermutation(values, pairs));
}