Я не полностью уверен, но я думаю, что следующее отвечает всем вашим особым ограничениям [надеюсь].
Функция случайного списка - это разновидность Фишера Йетса. Вы можете перекодировать его, чтобы использовать Дурстенфельд, если хотите.
Я не уверен, что ограничения могут быть выполнены чисто за один проход. То есть примените их , а , создав случайный список.
Я создал простой случайный список. Затем попытайтесь обнаружить / исправить (путем замены) некоторые нарушения ограничений.
Затем заполните отрицательными значениями, пытаясь исправить нарушения самоограничения, если это возможно.
Если это невозможно, повторите весь процесс.
В любом случае, вот моя версия. Я разделил большую функцию на несколько более мелких. Я также добавил функцию проверки и диагностический цикл. Это немного отличается от вашего, но другие ответы сделали то же самое:
#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;
}