如何用随机数填充数组以使它们不同？

Question

我有一个任务，我必须在随机索引中用 16 个随机数填充一个数组。

其中4个元素必须是-1，所有其他左边的索引必须是0-15，但与另一个不同，这意味着两个不同的索引不可能具有相同的数字（0-15） .

4个随机索引很容易，其他索引用0-15之间的随机数填充也很容易，但我怎么感觉它们之间必然不同？

还有两个条件使这个任务更加复杂，第一个是索引的编号不能在其中有相同的编号，这意味着 arr[3] == 3 是不可能的，另一个条件是

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

是我们必须处理的事情，这样它就不会发生。例如，如果 arr[2] == 0 和 arr[0] == 2，我们必须更改它，这样它就不会发生。

我很困惑，昨天我真的在这个面前坐了 8 个小时，尝试了各种各样的东西，老实说，我不知道..

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

我尝试使用 Fisher-Yates 洗牌方法，但出于某种原因，它甚至没有填充数组。不知道为什么

同时（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

我希望这会有所帮助，我试图与您的初稿和您的意图保持一致，只是要注意这应该适用于长度为 N 的数组。我第二次更改了条件以在放置值之前检查条件 - 现在您不需要遍历 set 数组并检查和更新值。

你也可以像这里评论的那样走另一种方式，只需在一个辅助数组的帮助下用值填充数组，以检查每个值只使用一次，然后在条件下随机交换索引。

我写下了这个，但我没有运行测试 - 所以请确保您了解发生了什么并根据您的需要升级它。我确实建议只使用一个辅助阵列，便于记忆，减少时间和检查。

祝你好运

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

Answer 2

我的 C 语言生疏了，我不想实现 Fisher-Yates 洗牌或处理 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) 的工作量。如果违反了您的最后一个约束条件，请拒绝该解决方案并重试。

Answer 3

我不是完全确定，但我认为以下满足您的所有特殊限制[希望如此]。

随机列表函数是 Fisher Yates 的变体。如果您愿意，可以重新编码以使用 Durstenfeld。

我不确定约束是否可以一次性完成。也就是说，应用它们而生成随机列表。

我所做的是生成一个简单的随机列表。然后，尝试 detect/fix（通过交换）一些约束违规。

然后，填充负值，尽可能修复自我约束违规。

如果做不到，重复整个过程。

无论如何，这是我的版本。我把大功能分成几个小功能。我还添加了一个检查功能和一个诊断循环。它与您的有很大不同，但其他答案也是如此：

#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 4

我对你的描述感到困惑。把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

Answer 5

我相信以下内容会生成约束的解决方案，并在所有满足约束的解决方案上均匀分布：

将数字 0 到 15 放入 A 组。
将数字 0 到 15 放入池 B。
12 次，从 A 池中抽取一个数字 a，从 B 池中抽取一个数字 b（在每种情况下均以均匀分布随机抽取并将抽取的数字从其池中移除，因此它以后不会再选）。分配 m[a] = b.
对于 A 池中剩余的四个号码 a 中的每一个，分配 m[a] = -1。
对于0到15（含）的所有i和i到15（含）的所有j，测试是否m[i] == j && m[j] == i（注意这个测试对于交换和 m[i] == i，因为它包括 i == j）。如果发现这种情况，则拒绝分配并从头开始重复算法。

我希望算法改进可以减少或消除拒绝频率，但这建立了一个基线正确的算法。

也可以使用单个池而不是两个池，并在分配 −1 元素时进行一些重新排列，但上面的算法更容易表达。

如何用随机数填充数组以使它们不同？

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

c

arrays

random

indexing

fill