Архив форумов ЦИТФорума

[МАКСИМ.]

Приветствую всех!
у меня есть проблема в создании алгоритма.
кто может мне помочь с какой задачкой?!

дан массив А[n] = { x[1],x[2],..x[i]..,x[n] },
где X[1] - 1-й элемент в массиве,
X[i] - i-й элемент в массиве,
.........................................
n - кол-во натур. чисел.

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

А то я уже бьюсь ЦЕЛЫЙ месяц!

[beliy]

самое простое на вскидку:
знаете как карты "бутербродом" перемешивают?
разделяем входной массив на 2 половины:

[GREA]

Периодически буду повторяться комбинации, думаю, таким способом

Самые простые способы перетасовки. Надежные но очень тупые или не оптимальные по скорости:
1)
Взять первое число массива i=0. Выбрать случайно число 0<=С<n (возможно совпадет с i). Поменять местами i-ый и C-ый элемент. Повторить
(можно делать прям в текущем массиве)

На всякий случай можно сделать несколько итераций, хотя и одной вроде хватит для полноценного перемешивания.


2)
(нужен второй - выходной, пустой в начале массив)
Выбрать случайно место для первого элемента в выходном массиве и скопировать его туда. Далее - выбрать случайно место для второго элемента (кроме занятых уже мест), и повторять, пока не скопируем все элементы в выходной массив.

[Aragaer]

"линейно-конгруэнтный" метод:
Выбрать число C, взаимнопростое с длиной массива и произвольное число N1. После чего i-й элемент поместить в ячейку номер C*i+N1 mod N (N - длина массива).
_________________
Open your eyes.
And Awaken.

[dipsy]

Надо написать рекурентную функцию для n элементов.
Для двух элементов, - можно перечислить рукамии.

Для трёх и более элементов, - берём первый элемент, - ставим на первое место, остальные перемешиваем.
Берём второй, ставим на первое место, - остальные n-1 перемешиваем.
Ну и т.д. Сколько бы элементов мы не взяли, - теоретически мы можем это всё перемешать.

Ни одна комбинация не повторится.
Другое дело, - то что кол-во вычислений здесь растёт как n! ( даже ещё быстрее, но это не важно ), - а значит это решение будет считаться плохим для компьютера, - т.к. надо, чтобы кол-во вычислений росло как n^2 в худшем случае.

[grf]

Количество комбинаций ограничено.
Тебе необходимо перебрать все комбинации или некоторое число их?
Или необходимо создать вид случайной комбинации, когда на первый взгляд комбинации разные, но они могут повторяться, например возмем четыре числа:
1 2 3 4
2 3 4 1 х
3 2 4 1
2 3 4 1 х
4 3 1 2
2 3 1 4

[GREA]