Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: проблема с комбинаторикой ;-)  (Прочитано 13619 раз)
0 Пользователей и 1 Гость смотрят эту тему.
МАКСИМ.
Гость
« : 07-04-2006 01:39 » 

привет всем!
я никак не могу составить алгоритм.
задачка такая :
дан массив
« Последнее редактирование: 07-04-2006 06:47 от Джон » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 07-04-2006 06:01 » 

Цитата
составить перестановку элементов в этом массиве.
всевозможные комбинации.
Вот тут не ясно.
« Последнее редактирование: 07-04-2006 06:47 от Джон » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #2 : 07-04-2006 06:46 » 

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

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

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

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Alf
Гость
« Ответ #3 : 07-04-2006 07:24 » 

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

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 07-04-2006 07:26 » 

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

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

http://www.ournet.md/~mio/tvpart1less3.html
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
МАКСИМ.
Гость
« Ответ #5 : 08-04-2006 09:22 » 

Цитата
составить перестановку элементов в этом массиве.
всевозможные комбинации.
Вот тут не ясно.
т.к. в 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 - кол-во комбинаций.
Записан
МАКСИМ.
Гость
« Ответ #6 : 08-04-2006 09:25 » 

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

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

зы У тебя точка в нике - опечатка или задумка?
необходимо чтоб все элементы присуствовали.
повторяющихся элементов в одной комбинации не должно быть!
 
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #7 : 08-04-2006 13:19 » 

Цитата
дан массив
Цитата
необходимо чтоб все элементы присуствовали.
повторяющихся элементов в одной комбинации не должно быть!
Имхо, не совсем точная формулировка. Ограничение повторяемости распространяется на содержимое массива или на порядковые номера элементов исходного массива при генерации комбинаций этих порядковых номеров (индексов)?
Скорее второе, ибо
Цитата
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]
но не уверен.

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 08-04-2006 13:40 » 

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

В случае, когда элементы массива неуникальны, полный перебор не совсем подходит - нужно дополнительно учитывать, что некоторые комбинации в случае полного перебора будут встречаться более 1 раза. Точно не помню, как это обходить, но что-то вроде сортировки массива и более хитрого прохода по массиву флагов - с учётом следующего элемента (если следующий равен текущему, то пропускаем текущий); можно и без сортировки, хотя оптимальнее наверное с ней.
« Последнее редактирование: 08-04-2006 13:44 от Вад » Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #9 : 08-04-2006 13:59 » 

задачка такая :
дан массив 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, - приходи, поможем.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
МАКСИМ.
Гость
« Ответ #10 : 10-04-2006 18:18 » 

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

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

ru
Offline Offline
Пол: Мужской

« Ответ #11 : 10-04-2006 19:06 » 

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

Кстати, по пути оформилось решение с отсортированным массивом, содержащим повторяющиеся элементы. Поправьте, если не прав, но достаточно будет ввести дополнительный критерий "если нет такого же незанятого элемента, стоящего перед текущим, то входить в рекурсию" (можно "перед" заменить на "после"). Для неотсортированного нужно будет производить поиск аналогичного "неиспользованного" элемента соответственно в одном из направлений до границы массива.
« Последнее редактирование: 10-04-2006 19:11 от Вад » Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #12 : 11-04-2006 03:12 » 

Яндекс.  Запрос 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
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #13 : 11-04-2006 20:37 » 

В свое время у меня была примерно такая же задача. Только чуть посложнее. Мне нужно было вытаскивать ряд не последовательно, а случайным образом. Заполнять массив рядов и вытаскивать из массива меня не очень радовало. Так как размер такого массива будет расти не пропорционально количеству элементов ряда. Я пошел чуть другим путем. Каждый ряд можно пронумеровать  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;
        }
}
« Последнее редактирование: 11-04-2006 20:49 от RXL » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines