How do I fill an array with random numbers such that they are different?

Question

I have a task where I have to fill an array with 16 random numbers, in random indexes.

4 of those elements have to be -1, and all the other left indexes have to be 0-15, but different from another, meaning it is impossible for two different indexes have the same number (0-15).

Filling 4 random indexes is easy, and so is filling the other indexes with random numbers between 0-15, but how do I feel them in such way that they are necessarily different from each other?

There are also two more conditions which complicate this task much more, the first one is that the number of the index cannot have the same number within it, meaning arr[3] == 3 is impossible, and another condition is that

    (m[p] == j && m[j] == mp && m != j)

is something that we must take care of so it won't happen. For example, if arr[2] == 0 and arr[0] == 2, we have to change it so it won't happen.

I'm so confused, I had literally sat 8 hours yesterday in front of this, trying all sort of things, and I have no idea, honestly..

void FillArray(int *sites, int length) 
{
    int checkarr[N] = { 0 };
    int i, 
        cnt = 0, 
        j = 0, 
        t = 0, 
        k, 
        times = 0;
    int *p = sites;

    while (cnt < C)
    {
        i = rand() % length;
        if (p[i] - 1)
            cnt = cnt;
        p[i] = -1;
        cnt++;
    }

    while (j < length) 
    {
        if (p[j] == -1) j++;
        else 
        {
            p[j] = rand() % length;
            checkarr[p[j]]++;
            j++;
        }
    }

    j =0;
    while (j<length)
    {
        for (k=0; k<length;k++)
        {
            while (checkarr[k] > 1)
            {
                while (t < length) 
                {
                    if (p[j] == p[t] && p[j] != -1 && j != t)
                    {
                        checkarr[p[t]]--;
                        p[t] = rand() % length;
                        checkarr[p[t]]++;
                        times++;
                    }
                    else t++;
                }

                if (times < 11) 
                { 
                    j++;
                    t = 0;
                    times = 0;
                }
            }
        }
    }
}

I tried using the Fisher-Yates shuffle method, but for somereason it doesn't even fill the array. I don't know why

while (j

    if (p[j] == -1)
        j++;
    else {
        while (m < length) {
            m = rand() % length;
            if (helpingArray[m] != -2)
            {
                p[j] = helpingArray[m];
                helpingArray[m] = -2;
                j++;
            }
            else if (helpingArray[m] == -2)
            {
                j = j;
            }

            for (w = 0; w < length; w++)
            {
                if (helpingArray[w] == -2)
                    count++;
            }
            if (count == 12) {
                m = length;
            }
        }
    }
}
}  

Answer 1

I believe the following generates a solution to the constraints with uniform distribution over all the solutions that satisfy the constraints:

• Put the numbers 0 to 15 in pool A.
• Put the numbers 0 to 15 in pool B.
• 12 times, draw a number a from pool A and a number b from pool B (in each case drawing randomly with uniform distribution and removing the drawn number from its pool, so it will not be chosen again later). Assign m[a] = b.
• For each of the four numbers a remaining in pool A, assign m[a] = -1.
• For all i from 0 to 15 (inclusive) and all j from i to 15 (inclusive), test whether m[i] == j && m[j] == i (note that this tests for both swaps and for m[i] == i, as it includes i == j). If such a case is found, reject the assignments and repeat the algorithm from the beginning.

I expect algorithmic improvements are possible to reduce or eliminate the frequency of rejection, but this establishes a baseline correct algorithm.

It is also possible to use a single pool instead of two and instead do some rearranging when the −1 elements are assigned, but the algorithm above is more easily expressed.

Answer 2

I'm not completely sure, but I think the following meets all your special constraints [hopefully].

The random list function is a variation on Fisher Yates. You could recode it to use Durstenfeld if you wish.

I'm not sure that the constraints can be done cleanly in a single pass. That is, apply them while generating the random list.

What I've done is to generate a simple random list. Then, try to detect/fix (by swapping) some of the constraint violations.

Then, fill with negative values, trying to fix the self constraint violations if possible.

If that can't be done, repeat the whole process.

Anyway, here is my version. I split up the large function into several smaller ones. I also added a check function and a diagnostic loop. It is quite a bit different from yours, but other answers did this as well:

#include <stdio.h>
#include <stdlib.h>

#define NEG     4

int opt_N;
int opt_v;
int opt_T;

#ifdef DEBUG
#define dbg(_fmt...) \
    do { \
        if (opt_v) \
            printf(_fmt); \
    } while (0)
#else
#define dbg(_fmt...)            /**/
#endif

// prtarray -- print array
void
prtarray(int *arr,int len)
{
    int idx;
    int val;
    int hangflg = 0;
    int cnt = 0;

    for (idx = 0;  idx < len;  ++idx) {
        val = arr[idx];
        if (val < 0)
            printf(" [%2.2d]=%d",idx,val);
        else
            printf(" [%2.2d]=%2.2d",idx,val);
        hangflg = 1;

        if (++cnt >= 8) {
            printf("\n");
            cnt = 0;
            hangflg = 0;
            continue;
        }
    }

    if (hangflg)
        printf("\n");
}

// fillrand -- generate randomized list (fisher yates?)
void
fillrand(int *arr,int len)
{
    char idxused[len];
    char valused[len];
    int fillcnt = 0;
    int idx;
    int val;

    for (idx = 0;  idx < len;  ++idx) {
        idxused[idx] = 0;
        valused[idx] = 0;
    }

    for (fillcnt = 0;  fillcnt < len;  ++fillcnt) {
        // get random index
        while (1) {
            idx = rand() % len;
            if (! idxused[idx]) {
                idxused[idx] = 1;
                break;
            }
        }

        // get random value
        while (1) {
            val = rand() % len;
            if (! valused[val]) {
                valused[val] = 1;
                break;
            }
        }

        arr[idx] = val;
    }
}

// swap2 -- swap elements that are (e.g.) arr[i] == arr[arr[i]])
int
swap2(int *arr,int len)
{
    int idx;
    int lhs;
    int rhs;
    int swapflg = 0;

    dbg("swap2: ENTER\n");

    for (idx = 0;  idx < len;  ++idx) {
        lhs = arr[idx];
        rhs = arr[lhs];

        // don't swap self -- we handle that later (in negfill)
        if (lhs == idx)
            continue;

        if (rhs == idx) {
            dbg("swap2: SWAP idx=%d lhs=%d rhs=%d\n",idx,lhs,rhs);
            arr[idx] = rhs;
            arr[lhs] = lhs;
            swapflg = 1;
        }
    }

    dbg("swap2: EXIT swapflg=%d\n",swapflg);

    return swapflg;
}

// negfill -- scan for values that match index and do -1 replacement
int
negfill(int *arr,int len)
{
    int idx;
    int val;
    int negcnt = NEG;

    dbg("negfill: ENTER\n");

    // look for cells where value matches index (e.g. arr[2] == 2)
    for (idx = 0;  idx < len;  ++idx) {
        val = arr[idx];
        if (val != idx)
            continue;

        if (--negcnt < 0)
            continue;

        // fill the bad cell with -1
        dbg("negfill: NEGFIX idx=%d val=%d\n",idx,val);
        arr[idx] = -1;
    }

    // fill remaining values with -1
    for (;  negcnt > 0;  --negcnt) {
        while (1) {
            idx = rand() % len;
            val = arr[idx];
            if (val >= 0)
                break;
        }

        dbg("negfill: NEGFILL idx=%d\n",idx);
        arr[idx] = -1;
    }

    dbg("negfill: EXIT negcnt=%d\n",negcnt);

    return (negcnt >= 0);
}

// fillarray -- fill array satisfying all contraints
void
fillarray(int *arr,int len)
{

    while (1) {
        // get randomized list
        fillrand(arr,len);

        if (opt_v)
            prtarray(arr,len);

        // swap elements that are (e.g. arr[i] == arr[arr[i]])
        while (1) {
            if (! swap2(arr,len))
                break;
        }

        // look for self referential values and do -1 fill -- stop on success
        if (negfill(arr,len))
            break;
    }
}

// checkarray -- check for contraint violations
// RETURNS: 0=okay
int
checkarray(int *arr,int len)
{
    int idx;
    int lhs;
    int rhs;
    int negcnt = 0;
    int swapflg = 0;

    dbg("checkarray: ENTER\n");

    if (opt_v)
        prtarray(arr,len);

    for (idx = 0;  idx < len;  ++idx) {
        lhs = arr[idx];
        if (lhs < 0) {
            ++negcnt;
            continue;
        }

        rhs = arr[lhs];

        if (rhs == idx) {
            printf("checkarray: PAIR idx=%d lhs=%d rhs=%d\n",idx,lhs,rhs);
            swapflg = 2;
        }

        if (lhs == idx) {
            printf("checkarray: SELF idx=%d lhs=%d\n",idx,lhs);
            swapflg = 1;
        }
    }

    if (negcnt != NEG) {
        printf("checkarray: NEGCNT negcnt=%d\n",negcnt);
        swapflg = 3;
    }

    dbg("checkarray: EXIT swapflg=%d\n",swapflg);

    return swapflg;
}

int
main(int argc,char **argv)
{
    char *cp;
    int *arr;

    --argc;
    ++argv;

    opt_T = 100;
    opt_N = 16;

    for (;  argc > 0;  --argc, ++argv) {
        cp = *argv;
        if (*cp != '-')
            break;

        switch (cp[1]) {
        case 'N':
            opt_N = (cp[2] != 0) ? atoi(cp + 2) : 32;
            break;

        case 'T':
            opt_T = (cp[2] != 0) ? atoi(cp + 2) : 10000;
            break;

        case 'v':
            opt_v = ! opt_v;
            break;
        }
    }

    arr = malloc(sizeof(int) * opt_N);

    for (int tstno = 1;  tstno <= opt_T;  ++tstno) {
        printf("\n");
        printf("tstno: %d\n",tstno);
        fillarray(arr,opt_N);
        if (checkarray(arr,opt_N))
            break;
        prtarray(arr,opt_N);
    }

    free(arr);

    return 0;
}

Answer 3

I am confused with your description. For placing N elements into N positions, I have a solution.

Question: Place N elements into N positions with constraints:

(1) arr[i] != i; 
(2) if arr[i] = j, then arr[j] != i

Solution: For current element i (0 <= i < N)

(1) Find candidate position count
    (a) count = N - i
    (b) if arr[i] is empty              =>    count -= 1
        else if arr[arr[i]] is empty    =>    count -= 1
(2) Select a random position from candidates
    (a) relative_index = random() % count
        (Note: relative_index means the position index in candidates)
    (b) Find absolute_index by searching candidates
        a candidate index j satisfies following constrains
            <1> arr[j] is empy
            <2> j != i
            <3> j != arr[i] when arr[i] is not empty

Answer 4

My C is rusty, and I don't want to implement a Fisher-Yates shuffle or deal with the bad behavior of C PRNGs, so I'm expressing the algorithm in pseudo-code. Okay, I lie. It's Ruby, but it reads like pseudo-code and is heavily commented to show the logic of the solution. Consider the comments to be the solution, and the stuff in between a concrete illustration that the algorithm being described actually works.

N = 16

# Create + populate an array containing 0,...,N-1
ary = Array.new(N) { |i| i }

# Shuffle it
ary.shuffle!  

# Iterate through the array.  If any value equals its index, swap it with
# the value at the next index, unless it's the last array element
ary.each_index { |i| ary[i], ary[i + 1] = ary[i + 1], ary[i] if ary.length - i > 1 && ary[i] == i }

# If the last element equals its index, swap it with any other element
# selected at random.  The rand function generates a random integer
# between 0, inclusive, and its argument, exclusive.
last = ary.length - 1
if ary[last] == last
  random_index = rand(last)
  ary[last], ary[random_index] = ary[random_index], ary[last]
end

# Replace 4 randomly selected entries with -1
4.times { ary[rand(ary.length)] = -1 }

# The array now contains unique elements (except for the -1's),
# none of which are equal to their index value
p ary

# Produces, e.g.:  [4, 10, -1, 5, 9, -1, 15, 14, 7, 8, 12, 1, -1, 0, -1, 2]

All of this takes O(N) work. If your last constraint is violated, reject the solution and retry.

Answer 5

I hope this will help, I tried to stay in the line with your first draft and what you were going for, just to note that this should work for an N length array. I changed the conditions on your second while to check the conditions before placing the value- and now you don't need to go over the set array and check and update the values.

you can also go another way as was commented here and just fill the array with values with help of one aux array to check each value is used only once and then randomly swap the indexes under the conditions.

I wrote this down but I didn't run tests- so make sure you understand whats going on and upgrade it to your needs. I do recommend using only one aux array, easy on memory and less whiles and checks.

GOOD LUCK

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 16
#define C 4

void FillArray(int *sites, int length) {
/*these aux arrays will keep track if an index was fill of if a value was used*/
int checkarrIndex[N] = { 0 };
int checkarrVal[N] = { 0 };

int i, cnt = 0, full=0; /*full is when all index are filled */
int *p = sites;
while (cnt < C) {
    i = rand() % length;
    if (checkarrIndex[i] == 0) /* checkarrIndex will let you know if an index has been gvin a value*/
    {
        ++checkarrIndex[i]; /*now  checkarrIndex[i] will be one so this index is now not valid for placement next time*/
        p[i] = -1;
        ++full;/*at the end of this while full will equal 4*/
        cnt++;
    }

}
while (full < length) /*here you need to draw a random index and a random value for it, 
                  not just a random value for a fixed index like you did, if I got this wrong just
                  go over the free indexes and place a rand value one at a time in the same manner*/
{
    int index; /*will store new random index */
    int value; /*will store new random value */
    index = rand() % N;
    value = rand() % N;/*max value is 15*/
    while(checkarrIndex[index]!= 0) /*check if this index was already placed */
    {
        index = rand() % N; /*try a another one */
    }
    /*I made this while loop to check all the con before filling the array */
    while(checkarrVal[value]!= 0 || p[value]== index || index == value) /*check if this value was already used  or if p[i]=j&&p[j]=i cond happens and make sure p[a] != a*/
    {
        value = rand() % N; /*try a another one */
    }
    ++checkarrIndex[index];/*set index as used */
    ++checkarrVal[value];/*set value as used */
    p[index] = value;
    ++full; /*another place was filled */


  }
}
static void PrintArray(int* arr, size_t size)
{
    int i = 0 ;
    for (i = 0 ; i< size; ++i)
    {
        printf("%d| ", arr[i]);
    }
    printf("\n");
}
int main(void)
{
    int array[N] = {0};
    FillArray(array, N);
    PrintArray(array, N);
    return 0;
}