CODEWITHSUNDEEP
javascriptarrays
Tiago
Tiago

Reputation: 4480

Finding a non-consecutive number pair in an array

Given an array with a minimum length of 3 and a maximum length of 5, which always contains uniquely occurring integers from 0 to 4 in ascending order, I need to pick out two non-consecutive numbers from it. Non-consecutive refers to their numeric value, not their position in the array.

To clarify, here are examples of valid arrays:

  1. [ 1, 2, 3 ]
  2. [ 0, 1, 2, 4 ]
  3. [ 0, 3, 4 ]

For the arrays above, valid answers could be, respectively:

  1. [ 1, 3 ]
  2. [ 0, 2 ], [ 0, 4 ] or [ 1, 4 ]
  3. [ 0, 3 ] or [ 0, 4 ]

Furthermore, in those cases where there is more than one valid answer, I need it to be selected at random, if at all possible (for instance I don't want to favor sequences that begin with the lowest number, which is what would occur if I always began checking from left to right and stopped checking as soon as I found one valid solution).

What would be the most efficient way of tackling this problem in Javascript?

Upvotes: 1

Views: 1149

Answers (5)

Bee157
Bee157

Reputation: 576

since you state that the array ellemnts are all unique, and that they are sorted.
It should suffice to take an random element

var index1=Math.floor(Math.random()*arr.length)

now any other element (except maybe the elemnts on position (index1 +/- 1) are not consecutive So a new random element can be chosen excluding the first index.

var index2=Math.floor(Math.random()*arr.length); 
if(index2==index1){
  index2+=((index2<arr.length-1)?1:-1);
}
if(Math.abs(arr[index1]-arr[index2])<=1){  
  if(index2==0 && arr.length<4){
    //set index2 to arr.length-1 and do check again, if not ok=> no result
    if(!(arr[index1]-arr[arr.length-1]>=-1)){
       return  [arr[arr.length-1],arr[index1]];
     }
  }
  else if(index2==arr.length-1 && arr.length<4){
     //set index2 to 0 and do check again, if not ok=> no result
     if(!(arr[index1]-arr[0]<=1)){
       return  [arr[0],arr[index1]];
     }
  }
  else{
    //if index2>index1 index2++
    //else index2--
    //always OK so no further check needed
    index2+=(index2>index1?1:-1);
    return [arr[index1],arr[index2]];
  }
}
else{
  //ok
  return [arr[index1,arr[index2]];
}
return false;

if speed is not important, you can use a filter on the array to calculate a new array with all elements differing more then 1 unit of arr[index1]. and randomly select a new number from this new array.

Other attempt

function getNonConsecutive(arr){
  var index1,index2,arr2;
  index1=Math.floor(Math.random()*arr.length);
  arr2=[].concat(arr);
  arr2.splice((index1!==0?index1-1:index1),(index!==0?3:2));
  if(arr2.length){
    index2=Math.floor(Math.random()*arr2.length);
    return [arr[index1],arr2[index2]];
  }
  else{
    //original array has length 3 or less
    arr2=[].concat(arr);
    arr2.splice(index1),1);
    for (var j=0,len=arr.length;j<len;j++){
      if(Math.abs(arr1[index1]-arr2[j])>1){
         return [arr[index1],arr2[j]];
      }
    }
  }
 return false
}

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386578

You could use two nested iterations and build an new array for choosing as random result.

function getNonConsecutives(array) {
    return array.reduce((r, a, i, aa) => r.concat(aa.slice(i + 2).map(b => [a, b])), []);
}

console.log(getNonConsecutives([ 0, 1, 2, 4 ]));
.as-console-wrapper { max-height: 100% !important; top: 0; }

According to Bee157's answer, you could use a random choice with a constraint, like length for the first index and add the needed space for the second index.

The problem is, due to the nature of choosing the first number first, the distribution of the result is not equal.

function getNonConsecutives(array) {
    var i = Math.floor(Math.random() * (array.length - 2));
    return [
        array[i],
        array[Math.floor(Math.random() * (array.length - 2 - i)) + 2 + i]
    ];
}

console.log(getNonConsecutives([ 0, 1, 2, 4 ]));

Upvotes: 1

Evan Trimboli
Evan Trimboli

Reputation: 30082

Something like this should do it:

const pick = nums => {
    // Pick a random number
    const val = nums[Math.floor(Math.random() * nums.length) + 0];
    // Filter out any numbers that are numerically consecutive
    const pool = nums.filter(n => Math.abs(n - val) > 1);
    // Pick another random number from the remainer
    const other = pool[Math.floor(Math.random() * pool.length) + 0];
    // Sort + return them
    return [val, other].sort();
};
console.log(pick([0, 1, 2, 4]));

Upvotes: 0

Nenad Vracar
Nenad Vracar

Reputation: 122047

You can create a function using recursion that will pick random number in each iteration and loop all other elements and if condition is met add to array.

function findN(data) {
  data = data.slice();
  var r = []

  function repeat(data) {
    if (data.length < 2) return r;
    var n = parseInt(Math.random() * data.length);

    data.forEach(function(e, i) {
      if (i != n) {
        var a = data[n];
        if (Math.abs(a - e) != 1 && r.length < 2) r.push(n < i ? [a, e] : [e, a])
      }
    })

    data.splice(n, 1);
    repeat(data)
    return r;
  }

  return repeat(data)
}

console.log(findN([1, 2, 3]))
console.log(findN([0, 1, 2, 4]))
console.log(findN([0, 3, 4]))

Upvotes: 0

Jeevika
Jeevika

Reputation: 142

demoFn(array) {
    var i,j, y =[];
    for (i=0; i<=array.length;i++) {
        for (j = i + 1; j <= array.length; j++) {
            if (array[j] && array[i]) {
                if (array[j] !== array[i] + 1) {
                    y.push([array[i], array[j]]);
                }
            }
        }
    }

}

Take a random array and check it.

Upvotes: 0

Related Questions