Как мне заполнить массив случайными числами, чтобы они были разными?

Надеюсь, это поможет, я старался придерживаться вашего первого черновика и того, к чему вы стремились, просто чтобы отметить, что это должно работать для массива длиной N. Я изменил условия на вашем втором этапе, чтобы проверить условия перед размещением значения - и теперь вам не нужно переходить по установленному массиву, проверять и обновлять значения.

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

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

УДАЧИ

#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;
}

Мой C заржавел, и я не хочу реализовывать тасование Фишера-Ятса или иметь дело с плохим поведением C PRNG, поэтому я выражаю алгоритм в псевдокоде. Ладно, вру. Это Ruby, но он читается как псевдокод и сильно комментируется, чтобы показать логику решения. Считайте комментарии решением, а то, что между ними - конкретной иллюстрацией того, что описываемый алгоритм действительно работает.

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]

Все это требует O (N) работы. Если ваше последнее ограничение нарушено, отклоните решение и повторите попытку.

Я не уверен, что полностью, но я думаю, что следующее отвечает всем вашим особым ограничениям [надеюсь].

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

Я не уверен, что ограничения можно сделать чисто за один проход. То есть применить их пока, генерируя случайный список.

Я создал простой случайный список. Затем попробуйте обнаружить / исправить (поменяв местами) некоторые нарушения ограничений.

Затем заполните отрицательными значениями, пытаясь по возможности исправить нарушения самозависимости.

Если это невозможно, повторите весь процесс.

Во всяком случае, вот моя версия. Я разделил большую функцию на несколько более мелких. Я также добавил функцию проверки и цикл диагностики. Он немного отличается от вашего, но другие ответы тоже:

#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;
}

Меня смущает ваше описание. Для размещения N элементов в N позиций у меня есть решение.

Вопрос: Поместите N элементов в N позиций с ограничениями:

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

Решение: Для текущего элемента 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

Я считаю, что следующее генерирует решение ограничений с равномерным распределением по всем решениям, которые удовлетворяют ограничениям:

• Поместите числа от 0 до 15 в пул A.
• Поместите числа от 0 до 15 в группу B.
• 12 раз вытяните число a из пула A и число b из пула B (в каждом случае случайное вытягивание с равномерным распределением и удаление выпавшего числа из его пула, чтобы оно не было выбрано позже). Назначают m[a] = b.
• Для каждого из четырех номеров a, оставшихся в пуле A, присвойте m[a] = -1.
• Для всех i от 0 до 15 (включительно) и всех j от i до 15 (включительно) проверьте, есть ли m[i] == j && m[j] == i (обратите внимание, что это тестирует как для свопов, так и для m[i] == i, поскольку он включает i == j). Если такой случай обнаружен, откажитесь от присвоений и повторите алгоритм сначала.

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

Также можно использовать один пул вместо двух и вместо этого выполнить некоторую перегруппировку, когда назначены элементы -1, но описанный выше алгоритм легче выразить.