Заполнить массив случайными непоследовательными числами

Question

Я хочу создать массив (indexes), который должен быть заполнен случайными числами от 0 до length - 1.

Таким образом, если length = 3;, то indexes должен увеличиться с 0 до 2 , например это может быть что-то вроде: [0, 2, 1].

И есть одно условие, которому мы должны следовать: (Боже, как я могу описать это на английском языке sh:)

Условие: Мы не принимаем последовательные числа.

Так что мы не должны возвращать:

[0, 1, 2]       => Because 0 and 1 and 2 are consecutive.

[2, 0, 1]       => Because 0 and 1 are consecutive.

[2, 3, 1, 0]    => Because 2 and 3 are consecutive.

Хорошо, я знаю, что может быть исключение, последний элемент может быть последовательным, потому что у нас нет выбора в этот момент!

Я написал код, но, к сожалению, он зависает в браузере из-за высокой загрузки ЦП!

Пожалуйста, помогите, мой ноутбук и я так запутались!

// generate number from 0 to max (max could include in the result)
function getRandom(max) {
    return Math.floor(Math.random() * (max + 1));
};

// our array to be filled with unordered numbers
let indexes = [];

// we will fill the above array with 0, 1 ,2 ,3 I mean 0 to (length - 1) 
let length = 4;

// loop through indexes so that it is filled with 4 elements
while( indexes.length <= length){

      // get a number randomally from 0 to 3
      let result = getRandom(length - 1);
       // we don't want any repeated number so..
       if(!indexes.includes(result)){     
          // finally here is our condition, we should   
          if( result !== indexes[indexes.length - 1] + 1 ){
              indexes.push(result);
          } else if(indexes.length == length){
            // push the last element to the array despite the condition
            indexes.push(result);
          }
       }

};

console.log(indexes);

Answer 1

Вы можете адаптировать современный алгоритм Фишера-Йейтса следующим образом:

, если обмен значениями в индексах i и j принесет значение по индексу i , которое там не разрешено из-за того, что уже было помещено в индекс i + 1 , тогда не делайте этот обмен , но вместо этого сделайте триплетный поворот между этими тремя задействованными индексами.

Вот реализация вместе с тестом из 400 запусков:

function shuffled(n) {
    let a = [...Array(n).keys()];
    for (let i = n - 1; i > 0; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        if (a[j]+1 === a[i+1]) { // a swap is going to violate the rule at i/i+1
            // Triple rotation at j, i, i+1 (or, when j == i, swap at i, i+1)
            a[j] = a[i];
            a[i] = a[i+1]--;
        } else { // standard swap
            let temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    // Finally check first two values:
    if (a[0]+1 === a[1]) {
        let temp = a[0];
        a[0] = a[1];
        a[1] = temp;
    }
    return a;
}

// Test this solution:
function verify(a) {
    let set = new Set(a);
    return !a.some((v, i) => v === a[i-1]+1 || !set.has(i));
}

for (let size = 2; size < 6; size++) {
    for (let i = 0; i < 100; i++) {
        let a = shuffled(size);
        if (!verify(a)) throw "not correct";
    }
}
console.log("tests successful");

Это имеет предсказуемую линейную сложность по времени. Нет риска множественных неудачных попыток.

Answer 2

Ваш алгоритм принимает случайные значения, и у вас есть проблема с последним значением, если единственным оставшимся значением является увеличенное значение значения до последнего значения.

Например, принятые значения 1, 0, 2 и оставшееся значение равно 3

          v
[1, 0, 2, 3]

В этом случае нет другого доступного значения, кроме нежелательного значения. Это приводит к бесконечному l oop.

---

. Вы можете взять массив всех индексов и использовать алгоритм случайного перемешивания Фишера-Йейтса и перемешивать до тех пор, пока не будут найдены последовательные приращения значений. массив.

function shuffle(array) { // https://stackoverflow.com/a/2450976/1447675
   var currentIndex = array.length,
       temporaryValue,
       randomIndex;

    // While there remain elements to shuffle...
    while (0 !== currentIndex) {
        // Pick a remaining element...
        randomIndex = Math.floor(Math.random() * currentIndex);
        currentIndex -= 1;

        // And swap it with the current element.
        temporaryValue = array[currentIndex];
        array[currentIndex] = array[randomIndex];
        array[randomIndex] = temporaryValue;
    }

    return array;
}

let length = 4,
    indices = Array.from({ length }, (_, i) => i);

do indices = shuffle(indices);
while (indices.some((v, i, a) => v + 1 === a[i + 1]))

console.log(...indices);

Answer 3

Обновлено:

Я сравнивал неправильное число для проверки непоследовательного правила

Вы можете создать список индексов, выбрать первый элемент случайным образом. затем удаляйте один элемент из индексов за раз, если выполняется условие или это последний элемент

const range = (n) => {
    const array = [];
    for (let  i = 0; i < n; i++) array.push(i);
    return array;
};

const randomIndex = (array) => (
    parseInt(array.length * Math.random())
);

const randomNonConsecutive = (n) => {
    const array = range(n);
    const result = array.splice(randomIndex(array), 1);

    while (array.length) {
        const last = result[result.length - 1];
        const next = last + 1;
        const index = randomIndex(array);
        const item = array[index];

        if (item !== next || array.length === 1) {
            result.push(item)
            array.splice(index, 1);
        }
    }

    return result;
}

console.log(randomNonConsecutive(3))
console.log(randomNonConsecutive(4))
console.log(randomNonConsecutive(5))

Answer 4

Поддерживается набор возможных номеров для выбора следующего номера.

Следующий номер, выбранный из этого набора, выбирается случайным образом.

Если выбран последовательный номер, то заказ поменялся местами.

Дублирование запрещено.

function randomNonConsecutive(upto) {
  const result = []
  let set = Object.keys([...Array(upto)])
  for(let x = 0; x < upto; x++) {
    let index = Math.floor(Math.random()*set.length)
    let insert = set[index]
    if(x > 0 && Number(result[x-1]) === insert-1) {
        [result[x-1], insert] = [insert, result[x-1]]
    }
    result[x] = insert
    set.splice(index,1)
  }
  return result
}

let result = randomNonConsecutive(10)
console.log(result)

Answer 5

При длине 4 ваш массив результатов имеет только несколько возможных результатов (см. Ниже).

Проблема с вашей функцией заключается в том, что если вы начнете с di git (s), который не даст никакого возможного ответа, он будет работать вечно, и только с 4 возможными числами вероятность этого очень велика. высокая. Если в качестве первого числа возвращается 0 или 3, решение никогда не будет найдено. То же самое, если возвращается 1, а второе число не равно 3, или если 2 является первым, а второе число не равно 0, и т.д.

Вы также будете работать вечно, потому что ваше время l oop должно использовать indexes.length < length вместо <=

[0, 1, 2, 3] // no
[0, 1, 3, 2] // no
[0, 2, 1, 3] // yes
[0, 2, 3, 1] // no
[0, 3, 1, 2] // no
[0, 3, 2, 1] // yes
[1, 0, 2, 3] // no
[1, 0, 3, 2] // yes
[1, 2, 3, 0] // no
[1, 2, 0, 3] // no
[1, 3, 0, 2] // yes
[1, 3, 2, 0] // yes
[2, 0, 1, 3] // no
[2, 0, 3, 1] // yes
[2, 1, 0, 3] // yes
[2, 1, 3, 0] // yes
[2, 3, 0, 1] // no
[2, 3, 1, 0] // no
[3, 0, 1, 2] // no
[3, 0, 2, 1] // yes
[3, 1, 0, 2] // yes
[3, 1, 2, 0] // no
[3, 2, 0, 1] // no
[3, 2, 1, 0] // yes

Это говорит нам о том, что этот алгоритм вероятен потерпеть неудачу, потому что не имеет обработки условия "сбой", когда не осталось чисел, которые могут удовлетворить условиям Вы могли бы проверить это и перезапустить, если это так, но, скорее всего, все будет медленно. Другой подход был бы лучше.