проблема с комбинаторикой ;-)

[МАКСИМ.]

привет всем!
я никак не могу составить алгоритм.
задачка такая :
дан массив �

[RXL]

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

Вот тут не ясно.

[Джон]

Я думаю - ему просто комбинации нужны, чтобы длинна оставалась. Или?

МАКСИМ., вот например есть 0101 - что надо с ним сделать? Вот это будет одной из комбинаций:
0
или
0000
или обязательно должны все элементы присутствовать?

зы У тебя точка в нике - опечатка или задумка?

[Alf]

Советую обратить внимание на книгу Ф. Новикова "Дискретная математика для программистов". Помнится, в разделе, посвященном комбинаторике, есть готовые алгоритмы генерации всех возможных перестановок элементов множества (с доказательством их корректности).

Если не удастся добыть в бумажном виде (настоятельно рекомендую, ее еще можно найти в продаже, и там вкратце приведен обзор разделов математики, которые просто обязан знать программист), могу прислать в отсканенном виде (около 3 Мб).

[RXL]

Знакомая задачка - когда-то тут же на форуме ее решали. Стоит попробовать поискать.
Так же тут можно поискать: https://club.shelek.ru/download.php?id=184

При помощи метода математической индукции можно доказать, что количество перестановок множества из n элементов равно: Pn = n!

http://www.ournet.md/~mio/tvpart1less3.html

[МАКСИМ.]

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

Вот тут не ясно.

т.к. в 2],....A[n]
я бы хотел составить комбинации из этих номеров.
например, n = 3.
то комбинации:
A[1]A[2]A[3]; A[1]A[3]A[2]; A[2]A[1]A[3];
A[2]A[3]A[1]; A[3]A[1]A[2]; A[3]A[2]A[1]
( порядок  не важен )
n!= 6 - кол-во комбинаций.

[МАКСИМ.]

Я думаю - ему просто комбинации нужны, чтобы длинна оставалась. Или?

МАКСИМ., вот например есть 0101 - что надо с ним сделать? Вот это будет одной из комбинаций:
0
или
0000
или обязательно должны все элементы присутствовать?

зы У тебя точка в нике - опечатка или задумка?

необходимо чтоб все элементы присуствовали.
повторяющихся элементов в одной комбинации не должно быть!
 

[Dimka]

дан массив

необходимо чтоб все элементы присуствовали.
повторяющихся элементов в одной комбинации не должно быть!

Имхо, не совсем точная формулировка. Ограничение повторяемости распространяется на содержимое массива или на порядковые номера элементов исходного массива при генерации комбинаций этих порядковых номеров (индексов)?
Скорее второе, ибо

A[1]A[2]A[3]; A[1]A[3]A[2]; A[2]A[1]A[3];
A[2]A[3]A[1]; A[3]A[1]A[2]; A[3]A[2]A[1]

но не уверен.

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

[Вад]

Я так понимаю, нужен полный перебор всех возможных комбинаций элементов массива
Если элементы уникальные, то заводится дополнительный массив с флагами для того, чтобы хранить индексы уже использованных элементы в процессе формирования перестановки.
Затем пишется функция с рекурсивным вызовом, в которой происходит проход по массиву флагов, и для каждого неиспользованного элемента: 1. выставляется флаг; 2. производится вызов функции; 3. снимается флаг.  Механизм хранения полученных перестановок и собственно остановки рекурсии в тот момент, когда перестановка полностью сформирована - по вкусу (я обычно передавал параметр - число оставшихся элементов - в функцию, после чего по достижении 0 производил запись куда нужно)

В случае, когда элементы массива неуникальны, полный перебор не совсем подходит - нужно дополнительно учитывать, что некоторые комбинации в случае полного перебора будут встречаться более 1 раза. Точно не помню, как это обходить, но что-то вроде сортировки массива и более хитрого прохода по массиву флагов - с учётом следующего элемента (если следующий равен текущему, то пропускаем текущий); можно и без сортировки, хотя оптимальнее наверное с ней.

[npak]

задачка такая :
дан массив 1],A[2],....A[n]
я бы хотел составить комбинации из этих номеров.
например, n = 3.
то комбинации:
A[1]A[2]A[3]; A[1]A[3]A[2]; A[2]A[1]A[3];
A[2]A[3]A[1]; A[3]A[1]A[2]; A[3]A[2]A[1]
( порядок  не важен )
n!= 6 - кол-во комбинаций.

 

Смотри, в чём вопрос.  Положим, A[1] == b и A[2] == b, тогда перестановки A[1]A[2]A[3] и A[2]A[1]A[3] совпадают и равны bbA[3], то есть одна и та же перестановка будет учтена дважды.  Если тебя не волнует, что некоторые перестановки будут учтены несколько раз, то задача решается так:
1.  возьми массив Ind размера N и заполни его в возростающем порядке числами от 1 до N
2.  Получи все перестановки массива Ind
3.  Для каждой перестановки массива Ind набор A[Ind[1]], A[Ind[2]], ... , A[Ind[N]] есть одна из искомых перестановок.

для случая N==3 получаем массив int Ind[] = {1,2,3}
Перестановки массива Ind {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1},{3,1,2},{3,2,1}
Соответствующие перестановки A есть
A[1]A[2]A[3]; A[1]A[3]A[2]; A[2]A[1]A[3];
A[2]A[3]A[1]; A[3]A[1]A[2]; A[3]A[2]A[1]


Перебрав все перестановки массива Ind получишь все перестановки массива A без учёта эквивалентности.  Если сам не сможешь написать, как перебирать массив целых от 1 до N, - приходи, поможем.

[МАКСИМ.]

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

таким образом. 
дан ряд натуральных чисел (1,2,3,.....n)
требуется составить все комбинации из чисел этого ряда.Причем все числа использовать один раз в каждой комбинации .А кол-во цифр в комбинации = n.
я думаю вопрос будет понятен.

[Вад]

МАКСИМ., во-первых, так не интересно, а во-вторых, твоя задача сводится к уже описанному. Еесли использовать тот подход, который описывал я, нужно создать как раз массив флагов размером N, обнулить все флаги и далее вызывать себе рекурсивную функцию, которая осуществляет проход по массиву флагов, и для каждого "незанятого" элемента выставляет флаг, добавляет текущий элемент (или индекс) на текущую позицию в "решение", производит рекурсивный вызов и снимает флаг. Писать здесь реализацию... Будет куда полезнее, если ты сам напишешь.

Кстати, по пути оформилось решение с отсортированным массивом, содержащим повторяющиеся элементы. Поправьте, если не прав, но достаточно будет ввести дополнительный критерий "если нет такого же незанятого элемента, стоящего перед текущим, то входить в рекурсию" (можно "перед" заменить на "после"). Для неотсортированного нужно будет производить поиск аналогичного "неиспользованного" элемента соответственно в одном из направлений до границы массива.

[npak]

Яндекс.  Запрос http://www.yandex.ru/yandsearch?rpt=rad&text=%E0%EB%E3%EE%F0%E8%F2%EC+%EF%E5%F0%E5%F1%F2%E0%ED%EE%E2%EA%E8

Один из результатов http://progpage.narod.ru/alg/per.html

[Finch]

В свое время у меня была примерно такая же задача. Только чуть посложнее. Мне нужно было вытаскивать ряд не последовательно, а случайным образом. Заполнять массив рядов и вытаскивать из массива меня не очень радовало. Так как размер такого массива будет расти не пропорционально количеству элементов ряда. Я пошел чуть другим путем. Каждый ряд можно пронумеровать  0...N. Где N будет факториал количества элементов ряда -1.
Теперь задача, как найти расположение ряда, зная его номер. В самом номере зашифровано расположение ряда.
Будем заполнять ряд последовательно. Начиная с первого элемента.
Первый элемент может встать на любое место ряда. Степень его свободы будет равно числу элементов ряда.
Второй и последуюшие элементы могут встать на любое не занятое место. При этом степень свободы их будет последовательно уменьшаться. Естественно последний элемент может встать только на одно единственное свободное место.
Вот я сейчас накидал программу, демострируюшую данный метод

Код:

#include<iostream.h>
#define MaxNum 4      //Константа количества элементов в ряду
int Buf[MaxNum];       //Собственно сам буфер, который будет заполняться.

int fact(int i)               // Функция подсчета факториала
{
        if (i==0)  return 1;
        int res=1;
        for (int k=1; k<=i; k++) res *=k;
        return res;
}


void FillBuf(int Num)                //Функция заполнения ряда
{
        int i=0;
        while (i<MaxNum) Buf[i++]=0;                   //Приводим буффер в начальное состояние
        i=1;
        int base=MaxNum;                              //переменная, характеризуешая текушую степень свободы
        int smesh;                                           //Переменная, характеризуюшая положение элемента ряда 
        int t;
        int beg;
        while (i<=MaxNum)                              //Перебираем последовательно все элементы ряда
        {
                smesh= Num % base;                 // Находим положение элемента в ряде
                t=-1;
                beg=-1;
                while (beg != smesh)                  //перебираем все пустые места
                {
                        t++;
                        if (Buf[t] == 0) beg++;
                }
                Buf[t]=i;                                                          //Вставляем элемент на пустое место
                Num /= base;                                                  // Переводим Индексное число, для показа состояния следуюшего элемента
                i++;                                                               // Переходим к следуюшемуэлементу
                base--;                                                           // Уменьшаем степень свободы.
        }

}

void main()
{
        int crc;
        int sum=fact(MaxNum);
        for(int i=0; i<sum; i++)                                               //Просто распечатываю все комбинации, плюс контрольное  число комбинации
        {
                FillBuf(i);
                crc=0;
                for (int k=0; k<MaxNum;k++) 
                {
                        crc=crc*MaxNum+Buf[k];
                        cout << Buf[k] << " ";
                }
                cout << " - " << crc << endl;
        }
}