nixp.ru v3.0

20 октября 2017,
пятница,
09:43:20 MSK

DevOps с компанией «Флант»
MXM написал 18 марта 2006 года в 05:57 (367 просмотров) Ведет себя как мужчина; открыл 1 тему в форуме, оставил 1 комментарий на сайте.

Приветствую всех!

у меня есть проблема в создании алгоритма.

кто может мне помочь с какой задачкой?!

дан массив А[n] = { x[1],x[2],..x..,x[n] },

где X[1] — 1-й элемент в массиве,

X — i-й элемент в массиве,

…………………………………..

n — кол-во натур. чисел.

нужно составить алгоритм , который бы

перемешивал все i в массиве.

причем каждая новая комбинация не повторялась.

откликнитесь кто лучше меня разбирается в комбинаторике.

мне нужен только принцып перетасовки.

спасибо за ранее!!!

Uncle Theodore

Не очень понятно, тебе нужно на выходе все N! (N факториал) возможных перестановок N элементов, или ты хочешь просто «перетасовать колоду» один раз? Второй вариант имеет большее отношение к генерации случайных чисел, чем к комбинаторике. Скажем, возьми простое число K меньшее N, на которое N НЕ делится. Потом бери

for(i=1;i

i*K (mod N) + 1

Получишь N разных чисел от 1 до N. Это и есть твоя перетасовка колоды.

Например, если у тебя 12 чисел, от 1 до 12

1 2 3 4 5 6 7 8 9 10 11 12

т.е. N = 12, и ты возьмешь K = 7, то перетасованный массив будет

8 3 10 5 12 7 2 9 4 11 6 1

Это — то, что ты хочешь?

Good Luck,

UT

MXM

привет !!!

спасибо что ответил .

мне нужно написать функцию которая выдает все варианты (N!)перестановки.

мне бы принцып перестановки .

rgo

Читай Кнута, у него в первом томе есть.

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

То есть, примерно так:

void swap (int i, int j, int arr[]) {
/* поменять местами arr[i] и arr[j] */
}
void permute (int *arr, int from, int size) {
    int i;
    for (i = from; i < size; i ++) {
        swap (from, i, arr); /* поменяем местами from и i-тый элты */
        permute (arr, from + 1, size);
        swap (from, i, arr); /* вернём всё как было */
    }
}
int main ()
{
    /* ... */
    permute (array, 0, N);
}

тут надо как-то приделать вывод получающихся перестановок. куда — не знаю, но можно. ;)