Перейти к содержимому


Фотография
- - - - -

задачка на комбинаторику


  • Авторизуйтесь для ответа в теме
Сообщений в теме: 39

#1 МАКСИМ.

МАКСИМ.

    Новичок

  • Новичок
  • Pip
  • 1 сообщений
  • 1 тем
  • Регистрация:18 Мар 2006

Отправлено 18 Март 2006 - 05:52

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

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

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

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

#2 Bolan

Bolan

    шволочь

  • Жильцы
  • PipPipPipPipPipPipPipPip
  • 3 296 сообщений
  • 54 тем
  • Регистрация:23 Сен 2005
  • Пол:Мужчина

Отправлено 18 Март 2006 - 12:42

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

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

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

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

в цикле проходишься по массиву. от одного до н. меняешь местами и-й элемент со случайно выбранным.
  • 0

#3 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 19 Март 2006 - 12:19

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

ууууууууууу
как все просто у тебя.....
есть одно увловие, которое ты забыл учесть (цитата) "причем каждая новая комбинация не повторялась."
:ooouh:
вот так
а без этого условия - это уже не комбинаторика , а голый рандомайз

в твоем случае вероятность совпадения компинаций - есть, хоть она и уменьшается при увеличении числа N

Пробую объяснить свой вариант
если не ошибаюсь, то число возможных компинаций N! (факториал)

резберем пример, чтобы проще объяснить алгоритм

пусть у нас 6 элементов: 1 2 3 4 5 6
число комбинаций 6!=6*5*4*3*2*1=720 комбинаций :blush:

пусть на есть функция FUNC которая возвращает итоговый массив исходя из номера комбинации
в нашем случае номера от 0-719

это функия делает примерно следующее (эта часть может варьироваться)
есть начальная - нулевая комбинация - 1 2 3 4 5 6
исходя из номера комбинации делаем следующие переборы начиная с самого левого

0 - 1 2 3 4 5 6
1 - 1 2 3 4 6 5 банальна переставляем
2 - 1 2 3 5 4 6 в след 4х главное заменить следующий (новый ) член ( 4 ку в данном случае)
3 - 1 2 3 5 6 4 на любой другой и проделать ту же операцию, что и в случае 2х элементов
4 - 1 2 3 6 5 4 тоесть банальная рекурсия с зафиксированным левым элементом
5 - 1 2 3 6 4 5

так же далее заменяя вледующий новый элемент, на все старые и перебираю оставшиеся - мы прийдем в 720 вариантам

при случае когда нам нужна допустим 710 комбинация - лучше иметь или обратный алгоритм или точки отсчета - например

точки отсчета
0 - 1 2 3 4 5 6
200 - 1 4 6 2 3 5 (придумал сам)
400
600

и все такое
единажды их высчитав...

вроде все
реализация за тобой...
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#4 zz7

zz7

    Двуликий Янус

  • Новичок
  • PipPipPipPipPipPip
  • 849 сообщений
  • 52 тем
  • Регистрация:14 Май 2004
  • Город:Колыбель космонавтики

Отправлено 20 Март 2006 - 15:07

Если n заранее известно, то n-вложенный цикл.
  • 0
Старший Брат смотрит на тебя!

#5 Bolan

Bolan

    шволочь

  • Жильцы
  • PipPipPipPipPipPipPipPip
  • 3 296 сообщений
  • 54 тем
  • Регистрация:23 Сен 2005
  • Пол:Мужчина

Отправлено 20 Март 2006 - 15:09

-=Silent=-Делов-то.Инициализируйте генератор псевдослучайных чисел номером перестановки.
  • 0

#6 zz7

zz7

    Двуликий Янус

  • Новичок
  • PipPipPipPipPipPip
  • 849 сообщений
  • 52 тем
  • Регистрация:14 Май 2004
  • Город:Колыбель космонавтики

Отправлено 20 Март 2006 - 15:29

2Болан:при большом n не поможет.
  • 0
Старший Брат смотрит на тебя!

#7 Bolan

Bolan

    шволочь

  • Жильцы
  • PipPipPipPipPipPipPipPip
  • 3 296 сообщений
  • 54 тем
  • Регистрация:23 Сен 2005
  • Пол:Мужчина

Отправлено 20 Март 2006 - 15:33

Зюзь, линейный конгруэнтный отлично работает при любой размерности чисел. И любой битности. Хватало б памяти. На число.
  • 0

#8 zz7

zz7

    Двуликий Янус

  • Новичок
  • PipPipPipPipPipPip
  • 849 сообщений
  • 52 тем
  • Регистрация:14 Май 2004
  • Город:Колыбель космонавтики

Отправлено 20 Март 2006 - 15:41

2Болан:Дело не в том, отличный ГСЧ или хрень с маком.Дело в том, что если ты инициируешь ГСЧ восьмеркой, и он дает тебе пять, то отсюда вовсе не следует, что больше он пять не выдаст, если ты будешь инициировать его другими числами.В указанной задаче, если следовать твоему алгоритму при n=6 и требуемых 720 комбинациях, получится, что ГСЧ повыдает числа согласно комбинаторным формулам, что, извините, бред.
  • 0
Старший Брат смотрит на тебя!

#9 Bolan

Bolan

    шволочь

  • Жильцы
  • PipPipPipPipPipPipPipPip
  • 3 296 сообщений
  • 54 тем
  • Регистрация:23 Сен 2005
  • Пол:Мужчина

Отправлено 20 Март 2006 - 16:20

2Болан:Дело не в том, отличный ГСЧ или хрень с маком.Дело в том, что если ты инициируешь ГСЧ восьмеркой, и он дает тебе пять, то отсюда вовсе не следует, что больше он пять не выдаст, если ты будешь инициировать его другими числами.

до прокрутки оставшихся чисел из диапазона - не выдаст. А там новый цикл.
  • 0

#10 zz7

zz7

    Двуликий Янус

  • Новичок
  • PipPipPipPipPipPip
  • 849 сообщений
  • 52 тем
  • Регистрация:14 Май 2004
  • Город:Колыбель космонавтики

Отправлено 20 Март 2006 - 16:29

до прокрутки оставшихся чисел из диапазона - не выдаст. А там новый цикл.

Какой новый цикл?? Ты собирался инициировать ГСЧ номером перестановки, вообще-то.В случае n=6 перестановок будет 720.То есть 720 инициаций.Которые, судя по твоим словам, неким магическим образом выдадут 720 различных перестановок.Пардон, но в сказки я не верю.
  • 0
Старший Брат смотрит на тебя!

#11 Bolan

Bolan

    шволочь

  • Жильцы
  • PipPipPipPipPipPipPipPip
  • 3 296 сообщений
  • 54 тем
  • Регистрация:23 Сен 2005
  • Пол:Мужчина

Отправлено 20 Март 2006 - 17:03

Какой новый цикл?? Ты собирался инициировать ГСЧ номером перестановки, вообще-то.В случае n=6 перестановок будет 720.То есть 720 инициаций.Которые, судя по твоим словам, неким магическим образом выдадут 720 различных перестановок.Пардон, но в сказки я не верю.

не верь. жалко шоли
  • 0

#12 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 20 Март 2006 - 19:41

2БоланТема у нас "задачка на комбинаторику"а ты решаешь задачу из темы "как решать в лоб и не думая"
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#13 (...)

(...)

    Новичок

  • Новичок
  • Pip
  • 8 сообщений
  • 1 тем
  • Регистрация:19 Авг 2005

Отправлено 22 Март 2006 - 00:26

Если собираешься использовать комбинации в дальнейшем, следовательно:1) либо придётся хранить в памяти все возможные комбинации; 2)либо запоминать комбинации, которые уже были.Второй способ вроде бы менее жадный (в смысле памяти), зато не предсказуем по времени (фиг его знает, как быстро он подберёт новую "оригинальную" комбинацию). Хотя, при достаточно большом N вероятность совпадения резко убывает.Первый способ сходу забирает память под все варианты, зато время выбора новой "оригинальной" комбинации сокращается. ИМХО имеет смысл при N достаточно маленьком.Думаю, алгоритм обоих вариантов понятен, но на всякий случай:В первом случае создаешь массив размером N!. методом перебора заполняешь элементы массива возможными комбинациями. Затем случайно выбираешь число-номер элемента массива. Значение данного элемента используешь, а сам элемент массива обнуляешь.Если выбран нулевой элемент массива, переходишь к следующему элементу (в порядке возрастания, если достиг конца массива, то сначала), пока не найдешь ненулевой элемент. Каждый раз, когда использовал какую-либо комбинацию увеличивай счётчик на единицу. Если счётчик стал равен размеру массива - уведоми пользователя.Во втором случае комбинацию элементов массива задавай через ГСЧ.Саму комбинацию записывай в конец созданной тобой строки в виде символов (надеюсь ты знаешь функции преобразования чисел в символы и наоборот). При следующем вызове задай комбинацию через ГСЧ. Проверь на равенство какой либо группе в строке.З.Ы. Вместо заморок со строками можно использовать массив, правда тогда выгоднее использовать первый вариант.Короче как всегда, либо прожорлевее, либо быстрее.
  • 0

#14 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 22 Март 2006 - 17:59

Если собираешься использовать комбинации в дальнейшем, следовательно:1) либо придётся хранить в памяти все возможные комбинации; 2)либо запоминать комбинации, которые уже были.Второй способ вроде бы менее жадный (в смысле памяти), зато не предсказуем по времени (фиг его знает, как быстро он подберёт новую "оригинальную" комбинацию). Хотя, при достаточно большом N вероятность совпадения резко убывает.Первый способ сходу забирает память под все варианты, зато время выбора новой "оригинальной" комбинации сокращается. ИМХО имеет смысл при N достаточно маленьком.Думаю, алгоритм обоих вариантов понятен, но на всякий случай:В первом случае создаешь массив размером N!. методом перебора заполняешь элементы массива возможными комбинациями. Затем случайно выбираешь число-номер элемента массива. Значение данного элемента используешь, а сам элемент массива обнуляешь.Если выбран нулевой элемент массива, переходишь к следующему элементу (в порядке возрастания, если достиг конца массива, то сначала), пока не найдешь ненулевой элемент. Каждый раз, когда использовал какую-либо комбинацию увеличивай счётчик на единицу. Если счётчик стал равен размеру массива - уведоми пользователя.Во втором случае комбинацию элементов массива задавай через ГСЧ.Саму комбинацию записывай в конец созданной тобой строки в виде символов (надеюсь ты знаешь функции преобразования чисел в символы и наоборот). При следующем вызове задай комбинацию через ГСЧ. Проверь на равенство какой либо группе в строке.З.Ы. Вместо заморок со строками можно использовать массив, правда тогда выгоднее использовать первый вариант.Короче как всегда, либо прожорлевее, либо быстрее.

Не что-то тут не тоКуда эти алгоритмы применять то? И как по ним узнать конкретное значение?Что-то ты не то говоришьИли не так...
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#15 zz7

zz7

    Двуликий Янус

  • Новичок
  • PipPipPipPipPipPip
  • 849 сообщений
  • 52 тем
  • Регистрация:14 Май 2004
  • Город:Колыбель космонавтики

Отправлено 24 Март 2006 - 15:02

троеточие все правильно сказал, только чрезмерно туманно. И размыто. Без конкретных алгоритмов.
  • 0
Старший Брат смотрит на тебя!

#16 M@D

M@D

    Новичок

  • Новичок
  • Pip
  • 6 сообщений
  • 1 тем
  • Регистрация:10 Фев 2006

Отправлено 25 Март 2006 - 00:41

нда....язык какой?
  • 0

#17 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 26 Март 2006 - 11:03

троеточие все правильно сказал, только чрезмерно туманно. И размыто. Без конкретных алгоритмов.

АГАА зачем нужно то это?Вопрос вроде в другом состоял
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#18 exact

exact

    Местный

  • Новичок
  • PipPipPipPip
  • 489 сообщений
  • 10 тем
  • Регистрация:01 Апр 2004

Отправлено 27 Март 2006 - 12:36

чтобы решить эту задачку лучше всего сделать два велосипедных спидометра и по порядку крутить колесики с правой стороны. ))))
  • 0
Почтенный шейх! Я ищу вас всю жизнь! Расскажите мне о магрибском молитвенном коврике!

#19 kostik

kostik

    Специалист ЦТО

  • Жильцы
  • PipPipPipPip
  • 410 сообщений
  • 10 тем
  • Регистрация:08 Янв 2005
  • Пол:Мужчина
  • Город:Msk-Klg

Отправлено 29 Март 2006 - 16:38

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

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

#20 exact

exact

    Местный

  • Новичок
  • PipPipPipPip
  • 489 сообщений
  • 10 тем
  • Регистрация:01 Апр 2004

Отправлено 31 Март 2006 - 11:04

Уже пошел глум.....

Хороший визуальный образ между прочим.В соседней теме в игру эрудит играют, так я давненько (еще когда компьютеры были большими) написал программку которая буковки перставляла .Тот же принцип. Комбинации чтобы не повторялись и сравнивались с базой словаря русских слов выдранной из socratа(логарифимической выборкой). Через рекурсию.Та же задача. Тот же спидометр. Только на колесиках 28 букв русского алфавита. Тривиальнейшая задача я бы сказал. Даже не понимаю что тут обсуждать столькоми постами.
  • 0
Почтенный шейх! Я ищу вас всю жизнь! Расскажите мне о магрибском молитвенном коврике!

#21 zz7

zz7

    Двуликий Янус

  • Новичок
  • PipPipPipPipPipPip
  • 849 сообщений
  • 52 тем
  • Регистрация:14 Май 2004
  • Город:Колыбель космонавтики

Отправлено 31 Март 2006 - 15:29

екзакд - голова!!
  • 0
Старший Брат смотрит на тебя!

#22 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 31 Март 2006 - 16:32

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

Может я никогда не видел велосипедного спидометра... Но помоему связи я вижу здесь малоМожет раз уж задача настолько тривиальна, то вы нам кусочек кода покажите...
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#23 exact

exact

    Местный

  • Новичок
  • PipPipPipPip
  • 489 сообщений
  • 10 тем
  • Регистрация:01 Апр 2004

Отправлено 03 Апрель 2006 - 10:36

екзакд - голова!!

zz7 - ты всегда прав

Может я никогда не видел велосипедного спидометра... Но помоему связи я вижу здесь мало

Может раз уж задача настолько тривиальна, то вы нам кусочек кода покажите...

непринципиально от велосипеда, можно от машины, или посмотри как крутятся колесики в электросчетчике

чтобы бы понятнее еще раз, то что бы в начале


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

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

а теперь возьми этот счетчик (можно мыслено) и могу тебя заверить что скольбы ты его не крутил, ни одна из комбинаций не разу не повторится ))))))))))))))))))))))
  • 0
Почтенный шейх! Я ищу вас всю жизнь! Расскажите мне о магрибском молитвенном коврике!

#24 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 03 Апрель 2006 - 22:01

zz7 - ты всегда правнепринципиально от велосипеда, можно от машины, или посмотри как крутятся колесики в электросчетчике чтобы бы понятнее еще раз, то что бы в началеа теперь возьми этот счетчик (можно мыслено) и могу тебя заверить что скольбы ты его не крутил, ни одна из комбинаций не разу не повторится ))))))))))))))))))))))

Открою один маленький секретесть принципиальная разница...колесики на спидометре ( которые меряют расстояние ) могут крутиться по одному...Тоесть из положения 1865 в положение 1866 ( к примеру ) в нашем же случае такому не быватьв нашем же случае будет что-то вроде 1865 -> 1856 , тоесть как минимум два колесика будут крутитьсяТоесть - сравнение не применимо....Мне кажется вы слишком легко восприняли задачу...Поэтому и предлагаю , чтобы вы ее реализовали раз она для вас такая простая...Здесь нужен алгоритм... Нормальный алгоритм...Который я и предложил в самом начале...
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#25 exact

exact

    Местный

  • Новичок
  • PipPipPipPip
  • 489 сообщений
  • 10 тем
  • Регистрация:01 Апр 2004

Отправлено 04 Апрель 2006 - 07:45

еще раз. )))

1 - колесо счетчика с нанесенными на нем элементами массива А[n] = { x[1],x[2],..x[i]..,x[n] }
2 - число таких колес в счетчике равно числу n (размерности массива A[n])
3 - крутите как спидометре.

где алгоритм решения не верен? искренне вас не понимаю.

Сообщение отредактировал exact: 04 Апрель 2006 - 08:05

  • 0
Почтенный шейх! Я ищу вас всю жизнь! Расскажите мне о магрибском молитвенном коврике!

#26 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 04 Апрель 2006 - 12:36

еще раз. )))

1 - колесо счетчика с нанесенными на нем элементами массива А[n] = { x[1],x[2],..x[i]..,x[n] }
2 - число таких колес в счетчике равно числу n (размерности массива A[n])
3 - крутите как спидометре.

где алгоритм решения не верен? искренне вас не понимаю.

Ё моЁ

в задание все прекрасно написано
Ключевое слово ПЕРЕМЕШИВАТЬ
тоесть если у нас есть массив 1234
то никак нельзя получить 4444 или 1233
Что с вашими колесиками неизбежно....

Ясно?

Сообщение отредактировал -=Silent=-: 04 Апрель 2006 - 12:37

  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#27 exact

exact

    Местный

  • Новичок
  • PipPipPipPip
  • 489 сообщений
  • 10 тем
  • Регистрация:01 Апр 2004

Отправлено 04 Апрель 2006 - 16:16

Ё моЁ

в задание все прекрасно написано
Ключевое слово ПЕРЕМЕШИВАТЬ
тоесть если у нас есть массив 1234
то никак нельзя получить 4444 или 1233
Что с вашими колесиками неизбежно....

Ясно?

Давайте не будем менять условия поставленной задачи .
Каждый , у кого в порядке с головой , может перечитать их в первом посте, открывшем тему.
В условии задачи не указано что нельзя получать "4444" или "1233".
Ключевое слово там - избежать повторения комбинаций .
  • 0
Почтенный шейх! Я ищу вас всю жизнь! Расскажите мне о магрибском молитвенном коврике!

#28 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 04 Апрель 2006 - 16:26

Давайте не будем менять условия поставленной задачи . Каждый , у кого в порядке с головой , может перечитать их в первом посте, открывшем тему.В условии задачи не указано что нельзя получать "4444" или "1233". Ключевое слово там - избежать повторения комбинаций .

Ха ха хаВот допустим у тебя есть яблоко, груша и апельсинОни лежат в таком порядкеГрушаЯблокоАпельсинТы их перемешалИ получилосьГрушаГрушаГрушаФокусник однако...
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#29 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 05 Апрель 2006 - 02:30

Существует несколько алгоритмов решения этой задачи.Один из них придумал еще некий Порфирий, живший в III веке. Порфирий построил «древо Порфирия», сейчас их называют деревья или «порфирианы». Также этот алгоритм напоминает всем известную «финансовую пирамиду».Смысл в том, что множество всех возможных n – перестановок, разбивается на n подмножеств, относя к одному подмножеству все те перестановки, у которых на первом месте стоит одно и то же число. В первое подмножество попадают все перестановки начинающиеся с 1, во второе – с 2 и т.д.В свою очередь образовавшиеся подмножества делятся на непересекающиеся подмножества.Процесс продолжается до тех пор, пока не появятся единичные перестановки. На рисунке таким образом показаны все перестановки для 1-2-3. 1 2 3 | | | | | | 2 3 1 3 1 2 | | | | | | 3 2 3 1 2 1Вот, еще один, похожий на предложенный -=Silent=-.Вводные понятия:1. Пара соседних чисел (в перестановке) называется упорядоченной, если первое число в паре меньше второго. В перестановке 1,3,5,4,2 первая с конца упорядоченная пара – (3,5)2. Первое число в этой паре – называется обрывающее (3)3. Перестановочный хвост – последовательность чисел, начиная с обрывающего и до конца. (3,5,4,2)4. Реупорядочить перестановочный хвост означает:4.1 заменить обрывающее число на наименьшее из перестановочного хвоста, превосходящее обрывающее (4,5,3,2)4.2 все остальные числа из перестановочного хвоста (во главе с обрывающим) расположить в порядке возрастания (4,2,3,5)Сам алгоритм:1. Открыть список перестановок перестановкой <1,2..,n>2. Проверять, есть ли в перестановке обрывающее число?3. если «ДА», то реупорядочить перестановочный хвост и записать результат4. «НЕТ» - решение закончено
  • 0
ЮРОДИВЫЙ

#30 exact

exact

    Местный

  • Новичок
  • PipPipPipPip
  • 489 сообщений
  • 10 тем
  • Регистрация:01 Апр 2004

Отправлено 05 Апрель 2006 - 07:14

пункт 3 bis :) если в полученной комбинации совпадают по значению любые два элемента массива,такую комбинацию считать недействительной.*примечание 3 bis - это к моему посту перед "грушами" silentap.s. А про Порфирия - интересно
  • 0
Почтенный шейх! Я ищу вас всю жизнь! Расскажите мне о магрибском молитвенном коврике!

#31 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 05 Апрель 2006 - 09:01

пункт 3 bis :) если в полученной комбинации совпадают по значению любые два элемента массива,такую комбинацию считать недействительной.*примечание 3 bis - это к моему посту перед "грушами" silenta

Это конечно решение, но есть одно но...Эффективность не та...пусть у нас n=50количество комбинаций 50!количество комбинаций "от колесиков" 50^50 (^ - степень )тоесть большую часть - а точнее 50^50 - 50! = 3,0414093201713378043612608166065e+64 (скопировал из калькулятора) - короче очень много...На меленьких размерах массива <10 - это может помочь, а дальше.......... :ku:
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#32 exact

exact

    Местный

  • Новичок
  • PipPipPipPip
  • 489 сообщений
  • 10 тем
  • Регистрация:01 Апр 2004

Отправлено 05 Апрель 2006 - 09:27

Это конечно решение, но есть одно но...Эффективность не та...

наконец то! :)

пусть у нас n=50количество комбинаций 50!количество комбинаций "от колесиков" 50^50 (^ - степень )тоесть большую часть - а точнее 50^50 - 50! = 3,0414093201713378043612608166065e+64 (скопировал из калькулятора) - короче очень много...На меленьких размерах массива <10 - это может помочь, а дальше..........

А эффективноть поднять не просто, а очень просто. Для этого досточно сделать колесики с "изменямым радиусом" :) . Временно убирать из массива элементов правого колесика, элементы "выпавшие" на колесиках слева.подумалось.Если про Порфирия в книжке написали, может на другое решение копирайт пора делать? :)
  • 0
Почтенный шейх! Я ищу вас всю жизнь! Расскажите мне о магрибском молитвенном коврике!

#33 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 05 Апрель 2006 - 09:40

наконец то! :) А эффективноть поднять не просто, а очень просто. Для этого досточно сделать колесики с "изменямым радиусом" :) . Временно убирать из массива элементов правого колесика, элементы "выпавшие" на колесиках слева.

Неа... :( Смотри ... Попробую объяснить данную ситуацию...Ты немного путаешь...Мы не собираем комбинацию из списка (массива) , а мы делаем перестановки в нем...пусть у нас 5 элементов... тоесть и все комбинации будут состоять именно из 5ти элементов...и если рассматривать твой вариант с "уменьшением радиуса", то для любого из колесиков, радиус будет равен 1 - тоесть только 1 элемент, так как остальные 4 уже стоят...Здесь не может идти речь о колесиках... это перестановки...как бы горизонтыльные "пятнашки" :ooouh: (как загнул ) ну похоже на них...

подумалось.Если про Порфирия в книжке написали, может на другое решение копирайт пора делать? :)

а у порфирия не было алгоритма... Это лишь способ представления...Что нам не сильно поможетТолько если увидеть графически...Должна быть какая-то зависимость...Тоесть - скажем как теорему в математике:Существует такая К ( а вернее N! таких ), для которых существует комбинация из n элеметов , такая, что она не равна ни одной из комбинаций для других KПонятное дело, что если алгоритм циклический, то F(5)=F(n!+5)

Сообщение отредактировал -=Silent=-: 05 Апрель 2006 - 10:09

  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#34 exact

exact

    Местный

  • Новичок
  • PipPipPipPip
  • 489 сообщений
  • 10 тем
  • Регистрация:01 Апр 2004

Отправлено 05 Апрель 2006 - 11:11

Неа... :( Смотри ... Попробую объяснить данную ситуацию...Ты немного путаешь...Мы не собираем комбинацию из списка (массива) , а мы делаем перестановки в нем...пусть у нас 5 элементов... тоесть и все комбинации будут состоять именно из 5ти элементов...и если рассматривать твой вариант с "уменьшением радиуса", то для любого из колесиков, радиус будет равен 1 - тоесть только 1 элемент, так как остальные 4 уже стоят...Здесь не может идти речь о колесиках... это перестановки...как бы горизонтыльные "пятнашки" :ooouh: (как загнул ) ну похоже на них...

пока не осмыслил то что ты написал дальше, но к тому что прочитал выше. В "спидометре" больше всего оборотов делает правое колесо. Вариант когда радиусы всех колес равны единице невозможен. Самое левое радиус неизменит никогда.
  • 0
Почтенный шейх! Я ищу вас всю жизнь! Расскажите мне о магрибском молитвенном коврике!

#35 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 06 Апрель 2006 - 23:13

Пример еще одного алгоритма представлен Здесь. Блок – схема и таблица первых перестановок.Все эти алгоритмы известны уже очень давно и общедоступны.
  • 0
ЮРОДИВЫЙ

#36 exact

exact

    Местный

  • Новичок
  • PipPipPipPip
  • 489 сообщений
  • 10 тем
  • Регистрация:01 Апр 2004

Отправлено 07 Апрель 2006 - 07:46

Пример еще одного алгоритма представлен Здесь. Блок – схема и таблица первых перестановок.Все эти алгоритмы известны уже очень давно и общедоступны.

откель первая блок-схема с алгоритмом?
  • 0
Почтенный шейх! Я ищу вас всю жизнь! Расскажите мне о магрибском молитвенном коврике!

#37 exact

exact

    Местный

  • Новичок
  • PipPipPipPip
  • 489 сообщений
  • 10 тем
  • Регистрация:01 Апр 2004

Отправлено 07 Апрель 2006 - 10:39

откель первая блок-схема с алгоритмом?

хотя вообщем неважно.алгоритм есть и тема закрыта
  • 0
Почтенный шейх! Я ищу вас всю жизнь! Расскажите мне о магрибском молитвенном коврике!

#38 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 07 Апрель 2006 - 14:55

Пример еще одного алгоритма представлен Здесь. Блок – схема и таблица первых перестановок.Все эти алгоритмы известны уже очень давно и общедоступны.

первый алгоритм с некоторым добавление представлен мной в первом моем сообщении на эту тему...Получать весь список - глупо... Так как память не резиновая - поэтому и нужна зависимость от какой-то входной переменной, что я пытаюсь ужа который раз всем объяснитьТоесть f(x) = комбинация...К этому второй алгоритм пока не приведен...
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#39 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 08 Апрель 2006 - 07:38

откель первая блок-схема с алгоритмом?

Взято из брошюры В.В. Шкурба "Задача трех станков" Изд - во "Наука" 1976.Похожий на алгоритм -=Silent=- видел в одной из книг Кнута (точно не помню какой том)
  • 0
ЮРОДИВЫЙ

#40 RItt

RItt

    Новичок

  • Новичок
  • Pip
  • 9 сообщений
  • 0 тем
  • Регистрация:14 Окт 2004

Отправлено 11 Апрель 2006 - 16:44

#include <iostream>template <typename T, size_t n>void f(T (&mas)[n]){	struct Temp	{		size_t		c_;		bool		pr_;		Temp() : c_(1), pr_(true) {}			} t[n];		t[n-1].c_=0;	while(true)	{		for(size_t j=0; j<n; ++j)			std::cout << mas[j] << " ";		std::cout << std::endl;		size_t  x = 0, i = 0;		while(t[i].c_==n-i)		{			t[i].c_ = 1;			if( (t[i].pr_ = !t[i].pr_) )				++x;			++i;		}				if(i+1 >= n)  break;				size_t k = t[i].c_;		if(!t[i].pr_)			k = n-i-k;		std::swap(mas[k+x-1], mas[k+x]);		++t[i].c_;	}}int main(){	int  mas[] = { 1, 2, 3, 4 };	f(mas);	return 0;}

Сообщение отредактировал RItt: 11 Апрель 2006 - 17:43

  • 0




Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анонимных