randomly reorder elements in an array without duplication

Question

I have a fixed array of sized nine and I am trying to reorder it randomly without duplication.

this is the following code:

class numbers{
    int randomIndexCount;
    public:
        void randomArray( int numArray[],int size){
            randomIndexCount = 0;               
            for (int i = 0; i < size; i++)
            {   
                int RandomIndex = rand() % size;
                randomIndexCount++;
                numArray[i] = numArray[RandomIndex];
                cout << numArray[i] <<endl;                 
            }           
    }

    int main(){
        srand(time(0));
        int numArray[9]= {1,2,3,4,5,6,0,0,0};
        numbers n;
        n.randomArray(numArray,9);
        return 0;
    }

So far I was able to reorder the array randomly with the given elements however I am unsure how to get rid of duplication. the output should be {1,2,3,4,5,6,0,0,0} but in a random order. I am unable to use the shuffle function and can only use rand. I am not sure how to remove duplicate entries

this is what I had in mind 1) with the given index check if that value already exist and if it does then skip this line " numArray[i] = numArray[RandomIndex];". however this approach would not be efficient as im sure this would be too time consuming. is there a way to remove duplicate values so my output is something like:

{0,1,0,6,2,0,5,3,4}

Removed duplicated manually and use en.cppreference.com/w/cpp/algorithm/random_shuffle — Rinat Veliakhmedov
– Rinat Veliakhmedov, Commented Mar 5, 2020 at 10:57
I am meant to create my own algorithm without using any shuffle functions — willzz100
– willzz100, Commented Mar 5, 2020 at 10:57
The brute force solution is quite easy. Do you care about performance? If yes you should sort the data, to be more efficient in removing duplicates. Then shuffle it again. It may be good to write 3 seperate functions for this. — Lukas-T
– Lukas-T, Commented Mar 5, 2020 at 11:04
@ZachSaw be cool buddy, He is asking for help, we all go through this kind of thing. — franvergara66
– franvergara66, Commented Mar 5, 2020 at 11:12

fern17 · Accepted Answer · 2020-03-05 11:04:25Z

1

You should swap elements in this line numArray[i] = numArray[RandomIndex];, not assigning. This will duplicate data! Here's the swap:

int v = numArray[i];
numArray[i] = numArray[RandomIndex];
numArray[RandomIndex] = v;

answered Mar 5, 2020 at 11:04

fern17

4976 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

franvergara66 · Accepted Answer · 2020-03-05 12:20:39Z

1

You are duplicating the elements with the assignement inside the for loop

numArray[i] = numArray[RandomIndex]

Instead asign the element to the position of the array, you need to swap those elements as follow:

class numbers
{
  int randomIndexCount;
public:
  void randomArray (int numArray[], int size)
  {
    randomIndexCount = 0;
    // Use srand with a time seed value in order to
    // have different results in each run of the programm
    srand (time (NULL));
    for (int i = 0; i < size - 1; i++)
      {
    int swap = numArray[i];
    //take a random index from 0 to i  
    int j = rand () % (size);
      numArray[i] = numArray[j];
      numArray[j] = swap;
      cout << numArray[i] << endl;
      }
  }
};

int main ()
{
  int numArray[9] = { 1, 2, 3, 4, 5, 6, 0, 0, 0 };
  numbers n;
  n.randomArray (numArray, 9);
  return 0;
}

This will be the output that includes all then numbers in the array:

edited Mar 5, 2020 at 12:20

answered Mar 5, 2020 at 11:22

franvergara66

10.8k21 gold badges61 silver badges102 bronze badges

2 Comments

willzz100 Over a year ago

The output should contain all the numbers in the array in a random order 1-6 and 0,0,0

willzz100 Over a year ago

tested it out and still has duplicate numbers and only prints out 8 numbers instead of 9

CiaPan · Accepted Answer · 2020-03-13 13:50:51Z

1

This loop scans positions from the end of the array towards its beginning and randomly selects a new item to be put at the current position. Items are chosen from positions not scanned yet.

This way every place is exactly once chosen to be filled with some item, and each item is exactly once placed in its final position (although, before this happens, it may be several times swapped out of places chosen for other elements).

It also guarantees no item disappears (gets overwritten) and no duplicates appear (no item is copied inadvertently) - if you have duplicates in input data, the same duplicates remain in the output (although permuted); if there are no duplicates, there will be no duplicates.

Additionally, if the rand() function has no bias, every item has the same chance to end at any chosen position, hence each possible permutation is equally probable as an output.

for (int i = size; i > 1; -- i)
{
    int swapIndex = rand() % i;

    int swap = numArray[swapIndex];
    numArray[swapIndex] = numArray[i-1];
    numArray[i-1] = swap;
}

edited Mar 13, 2020 at 13:50

answered Mar 5, 2020 at 11:34

CiaPan

9,5802 gold badges23 silver badges38 bronze badges

3 Comments

willzz100 Over a year ago

this code is half correct, it removed duplication however only prints out 8 elements not 9

CiaPan Over a year ago

@willzz100 This code does print nothing, it only permutes an array.

CiaPan Over a year ago

@willzz100 I have expanded a description of the loop's properties, hopefully it is useful.

Collectives™ on Stack Overflow

randomly reorder elements in an array without duplication

3 Answers 3

Comments

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related