How to Shuffle an Array So That No Two Consecutive Values Are the Same

How to shuffle an array of numbers without two consecutive elements repeating?

May not be technically the best answer, hopefully it suffices for your requirements.

import numpy as np
def generate_random_array(block_length, block_count):
    for blocks in range(0, block_count):
        nums = np.arange(block_length)
        np.random.shuffle(nums)
        try:
            if nums[0] == randoms_array [-1]:
                nums[0], nums[-1] = nums[-1], nums[0]
        except NameError:
            randoms_array = []
        randoms_array.extend(nums)
    return randoms_array


generate_random_array(block_length=1000, block_count=1000)

Is there a way to shuffle an array so that no two consecutive values are the same?

Despite appearances, this is non-trivial. As the commentator @antonio081014 points out, it's actually an algorithmic question, and (as @MartinR points out) is addressed here. Here's a very simple heuristic that (unlike the solution from @appzYourLife) is not an algorithm, but will work in most cases, and is much faster (O(n^2) rather than O(n!)). For randomness, simply shuffle the input array first:

func unSort(_ a: [String]) -> [String] {
    // construct a measure of "blockiness"
    func blockiness(_ a: [String]) -> Int {
        var bl = 0
        for i in 0 ..< a.count {
            // Wrap around, as OP wants this on a circle
            if a[i] == a[(i + 1) % a.count] { bl += 1 } 
        }
        return bl
    }
    var aCopy = a // Make it a mutable var
    var giveUpAfter = aCopy.count // Frankly, arbitrary... 
    while (blockiness(aCopy) > 0) && (giveUpAfter > 0) {
        // i.e. we give up if either blockiness has been removed ( == 0)
        // OR if we have made too many changes without solving

        // Look for adjacent pairs    
        for i in 0 ..< aCopy.count {
            // Wrap around, as OP wants this on a circle
            let prev = (i - 1 >= 0) ? i - 1 : i - 1 + aCopy.count
            if aCopy[i] == aCopy[prev] { // two adjacent elements match
                let next = (i + 1) % aCopy.count // again, circular 
                // move the known match away, swapping it with the "unknown" next element
                (aCopy[i], aCopy[next]) = (aCopy[next], aCopy[i])
            }
        }
        giveUpAfter -= 1
    }
    return aCopy
}

var colors = ["blue", "red", "green", "red", "blue", "blue", "blue", "green"]
unSort(colors) // ["blue", "green", "blue", "red", "blue", "green", "blue", "red"]

// Add an extra blue to make it impossible...
colors = ["blue", "blue", "green", "red", "blue", "blue", "blue", "green"]
unSort(colors) //["blue", "green", "blue", "red", "blue", "blue", "green", "blue"]

Rearrange array so that no adjacent values are the same in PHP

Here is my first method that aims to minimize looping to achieve the required outcome.

Code: (Demo with 3 different arrays and echo & var_export throughout the process)

// add $array here
$length=sizeof($array);
shuffle($array);
$valcounts=array_count_values($array);

function consec_check($array){
    $loops=sizeof($array)-1; // last element will not have right side element for comparison
    for($i=0; $i<$loops; ++$i){
        if($array[$i]==$array[$i+1]){
            return false;  // consecutive equal values = invalid
        }
    }
    return true;
}

if(max($valcounts)<=ceil($length/2)){  // if logically possible to fix
    while(!consec_check($array)){  // while any two equal elements are consecutive          
        foreach(array_diff($valcounts,[1]) as $color=>$count){  // only bother with elements that occur more than once
            $colorkeys=array_keys($array,$color);  // color group keys
            for($i=0; $i<$count; ++$i){
                if($i>0 && $prevk+1==$colorkeys[$i]){  // identify consecutives elements with same color
                    if($colorkeys[0]!=0){  // safe to shift {$colorkeys[$i]} to first position
                        array_unshift($array,array_splice($array,$colorkeys[$i],1)[0]);
                    }elseif(end($colorkeys)!=$length-1){  // safe to push {$colorkeys[$i]} to the last position
                        array_push($array,array_splice($array,$colorkeys[$i],1)[0]);
                    }else{  // no easy option, find a safe location inside array (more frequently used as array length increases)
                        for($j=0; $j<$count; ++$j){
                            if($j>0 && $colorkeys[$j]-$prevj>3){  // if 3 off-colors between two elements                                   array_splice($array,$prevj+2,0,array_splice($array,$colorkeys[$i],1));
                                break;                          
                            }
                            $prevj=$colorkeys[$j];
                        }
                    }
                    $colorkeys=array_keys($array,$color);  // update color keys array for continued processing
                }
                $prevk=$colorkeys[$i];
            }
        }
    }
    var_export($array);  // valid
}else{
    echo "\n\n<a href=\"https://www.youtube.com/watch?v=XAYhNHhxN0A\">Array cannot be made valid.</a>";
}

And here is my second method that uses regex patterns.

Code: (Demo with 3 different arrays and echo & var_export throughout the process)

shuffle($array);
$string=implode(' ',$array);
$start_length=strlen($string);

foreach(array_unique($array) as $v){
    $pullcount=$pushcount1=$pushcount2=0;
    $string=preg_replace("/$v (?=$v)/","",$string,-1,$pullcount);  // remove the first value of each conflicting pair
    $string=preg_replace("/ \K(?<!$v )(?!$v)|^(?!$v)/","$v ",$string,$pullcount,$pushcount1);  // foreach removal, re-insert value(s) where valid
    if($pullcount<=$pushcount1){
        $string=preg_replace("/$(?<!$v)/"," $v",$string,$pullcount-$pushcount1,$pushcount2);
    }
    if($pullcount!=$pushcount1+$pushcount2){
        echo "failure while replacing $v $pullcount & ",$pushcount1+$pushcount2,"\n";
        break;
    }else{
        echo "successfully replaced $pullcount conflicts for $v\n";
    }
}

if($start_length==strlen($string)){
    $array=explode(" ",$string);
    var_export($array);
}else{
    echo "\n<a href=\"https://www.youtube.com/watch?v=XAYhNHhxN0A\">Array cannot be made valid.</a>";
}

My second method wins on brevity, but it may not be trustworthy in other cases where values contain spaces or when a value is a substring of another value.

Both methods avoid the possibility of an infinite loop and will indicate if the array cannot be made valid.

Ruby. Shuffle the array so that there are no adjacent elements with the same value

The simple and maybe the less effective way could be the brute force.

So on a simplified version of the array, one can do:

ary = %w(a a c c b a s)

loop do
  break if ary.shuffle!.slice_when { |a, b| a == b }.to_a.size == 1
end

Some check should be added to assure that a solution exists, to avoid infinite loop.

Other (better?) way is to shuffle then find the permutation (no infinite loop) which satisfy the condition:

ary.shuffle!    
ary.permutation.find { |a| a.slice_when { |a, b| a == b }.to_a.size == 1 }

If a solution does not exist, it returns nil.

Run the the benchmark:

def looping
  ary = %w(a a c c b a s)
  loop do
    break if ary.shuffle!.slice_when { |a, b| a == b }.to_a.size == 1
  end
  ary
end

def shuffle_permute
  ary = %w(a a c c b a s)
  ary.shuffle!
  ary.permutation.lazy.find { |a| a.slice_when { |a, b| a == b }.to_a.size == 1 }
end

require 'benchmark'

n = 500
Benchmark.bm do |x|
  x.report { looping }
  x.report { shuffle_permute }
end

Fill an array with random non-consecutive numbers

Your algorithm takes random values and you have a problem with the last value, if the only left over value is the incremented value of the value before the last value.

For example, the taken values are 1, 0, 2 and leftover value is 3

          v
[1, 0, 2, 3]

In this case, there is no other value available, than an unwanted value. This yields to an infinite loop.

You could take an array of all indices and use a Fisher-Yates shuffle algorithm and shuffle until no consecutive incrementing values are in the array.

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);

Randomizing set of duplicate arrays in Java without repeating elements

This is a heuristic solution for random shuffling not allowing consecutive duplicates. It applies to lists, but it's easy to transfer it to arrays as it does only swapping and no shift operations are required. It seems to work in the majority of cases for lists consisting of millions of elements and various density factors, but always keep in mind that heuristic algorithms may never find a solution. It uses logic from genetic algorithms, with the exception that this version utilizes one individual and selective mutation only (it's easy to convert it to a real genetic algorithm though), but it's simple and works as follows:

If a duplicate is found, try swapping it with a random element after it; if not possible, try swapping it with an element prior to it (or vice versa). The key point here is the random position for exchanging elements, so as to keep a better uniform distribution on random output.

This question has been asked in alternative forms, but I couldn't find an acceptable solution yet. Unfortunately, as most of the proposed answers (except for the "greedy" extensive re-shuffling till we get a match or computing every combination), this solution does not provide a perfect uniform distribution, but seems to minimize some patterns, :( still not possible to remove every pattern, as you see below. Try it and post any comments for potential improvements.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Random;

//Heuristic Non-Consecutive Duplicate (NCD) Shuffler
public class NCDShuffler {

    private static Random random = new Random();
    //private static int swaps = 0;

    public static <T> void shuffle (List<T> list) {
        if (list == null || list.size() <= 1) return;
        int MAX_RETRIES = 10; //it's heuristic
        boolean found;
        int retries = 1;
        do {
            Collections.shuffle(list);
            found = true;
            for (int i = 0; i < list.size() - 1; i++) {
                T cur = list.get(i);
                T next  = list.get(i + 1);
                if (cur.equals(next)) {

                    //choose between front and back with some probability based on the size of sublists
                    int r = random.nextInt(list.size());
                    if ( i < r) {
                        if (!swapFront(i + 1, next, list, true)) {
                            found = false;
                            break;
                        }
                    } else {
                        if (!swapBack(i + 1, next, list, true)) {
                            found = false;
                            break;
                        }
                    }
                }
            }
            retries++;
        } while (retries <= MAX_RETRIES && !found);

    }

    //try to swap it with an element in a random position after it
    private static <T> boolean swapFront(int index, T t, List<T> list, boolean first) {
        if (index == list.size() - 1) return first ? swapBack(index, t, list, false) : false;
        int n = list.size() - index - 1;
        int r = random.nextInt(n) + index + 1;
        int counter = 0;
        while (counter < n) {
            T t2 = list.get(r);
            if (!t.equals(t2)) {
                Collections.swap(list, index, r);
                //swaps++;
                return true;
            }
            r++;
            if (r == list.size()) r = index + 1;
            counter++;
        }

        //can't move it front, try back
        return first ? swapBack(index, t, list, false) : false;
    }

    //try to swap it with an element in a random "previous" position
    private static <T> boolean swapBack(int index, T t, List<T> list, boolean first) {
        if (index <= 1) return first ? swapFront(index, t, list, false) : false;
        int n = index - 1;
        int r = random.nextInt(n);
        int counter = 0;
        while (counter < n) {
            T t2 = list.get(r);
            if (!t.equals(t2) && !hasEqualNeighbours(r, t, list)) {
                Collections.swap(list, index, r);
                //swaps++;
                return true;
            }
            r++;
            if (r == index) r = 0;
            counter++;
        }
        return first ? swapFront(index, t, list, false) : false;
    }

    //check if an element t can fit in position i
    public static <T> boolean hasEqualNeighbours(int i, T t, List<T> list) {
        if (list.size() == 1) 
            return false;
        else if (i == 0) {
            if (t.equals(list.get(i + 1)))
                return true;
            return false;
        } else {
            if (t.equals(list.get(i - 1)) || (t.equals(list.get(i + 1))))
                return true;
            return false;
        }
    }

    //check if shuffled with no consecutive duplicates
    public static <T> boolean isShuffledOK(List<T> list) {
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i).equals(list.get(i - 1)))
                return false;
        }
        return true;
    }
    //count consecutive duplicates, the smaller the better; We need ZERO
    public static <T> int getFitness(List<T> list) {
        int sum = 0;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i).equals(list.get(i - 1)))
                sum++;
        }
        return sum;
    }

    //let's test it
    public static void main (String args[]) {
        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        //initialise a list
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(3);

        /*for (int i = 0; i<100000; i++) {
            list.add(random.nextInt(10));
        }*/

        //Try to put each output in the frequency Map
        //then check if it's a uniform distribution
        Integer hash;
        for (int i = 0; i < 10000; i++) {
            //shuffle it
            shuffle(list);

            hash = hash(list);
            if (freq.containsKey(hash)) {
                freq.put(hash, freq.get(hash) + 1);
            } else {
                freq.put(hash, 1);
            }
        }
        System.out.println("Unique Outputs: " + freq.size());
        System.out.println("EntrySet: " + freq.entrySet());
        //System.out.println("Swaps: " + swaps);
        //for the last shuffle
        System.out.println("Shuffled OK: " + isShuffledOK(list));
        System.out.println("Consecutive Duplicates: " + getFitness(list));
    }

    //test hash
    public static int hash (List<Integer> list) {
        int h = 0;
        for (int i = 0; (i < list.size() && i < 9); i++) {
            h += list.get(i) * (int)Math.pow(10, i); //it's reversed, but OK
        }
        return h;
    }
}

This is a sample output; it's easy to understand the issue with the non-uniform distribution.

Unique Outputs: 6

EntrySet: [1312=1867, 3121=1753, 2131=1877, 1321=1365, 1213=1793, 1231=1345]

Shuffled OK: true

Consecutive Duplicates: 0

Shuffle an array of unequally repeating entries, so they do not repeat

I devised an algorithm that should do what you're asking for. Given a sequence, it will randomly reorder it such that no value repeats. However, it does appear to have a tendency to create repeated sub-sequences (e.g. ..."A" "B" "C" "A" "B" "C"...). I wrapped it in a function reorder_no_reps:

function seq = reorder_no_reps(seq)

  % Find unique values and counts:
  N = numel(seq);
  [vals, ~, index] = unique(seq(:), 'stable');
  counts = accumarray(index, 1);
  [maxCount, maxIndex] = max(counts);

  % Check the maximum number of occurrences:
  if (2*maxCount-1 > N)
    error('Can''t produce sequence without repeats!');
  end

  % Fill cell array column-wise with permuted and replicated set of values:
  C = cell(maxCount, ceil(N/maxCount));
  if (3*maxCount-1 > N)
    permIndex = [maxIndex(1) ...
                 setdiff(randperm(numel(vals)), maxIndex(1), 'stable')];
  else
    permIndex = randperm(numel(vals));
  end
  C(1:N) = num2cell(repelem(vals(permIndex), counts(permIndex)));

  % Transpose cell array and extract non-empty entries:
  C = C.';
  seq = reshape([C{~cellfun('isempty', C)}], size(seq));

end

A description of the steps for the algorithm:

Find the unique values in the input sequence (vals) and how many times they each appear (counts).
Find the maximum occurrence of a single value (maxCounts) and check if it is too large to make a sequence without repreats.
A random permutation order is applied to both the unique values and their counts. If the maximum occurrence exceeds a given threshold, the corresponding value index is moved to the beginning of the randomized order (the reason why is addressed in the next bullet).
Each unique value is then replicated in place by its number of occurrences in the sequence. A cell array is filled in column-wise order with these replicated values, possibly leaving some cells at the end empty. Since the cell array has a number of rows equal to the maximum occurrence of a value, no single row of the resulting cell array will have a value appearing more than once in it. In addition, the last value in each row should be different than the first value in the subsequent row (ensured by filling first with the most frequently occurring value in certain cases).
Transpose the cell array, then pull all the non-empty cell values in column-wise order and reshape them into the same size as the input sequence. This is the same as pulling values row-wise from the non-transposed cell array, which should give you a sequence without repeated values.