Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Номер комбинации перестановки - Мир MS Excel

Старая форма входа
  • Страница 1 из 2
  • 1
  • 2
  • »
Модератор форума: китин  
Мир MS Excel » Работа и общение » Мозговой штурм » Номер комбинации перестановки
Номер комбинации перестановки
Принимаете участие?
Светлый Дата: Четверг, 25.08.2016, 13:30 | Сообщение № 1
Группа: Друзья
Ранг: Старожил
Сообщений: 1821
Репутация: 506 ±
Замечаний: 0% ±

Excel 2013, 2016
Всем доброго дня!
Опять решил подбросить дров в интеллектуальные костры участников МШ.
Когда-то помогал сыну с задачками по комбинаторике и придумал и реализовал алгоритм, который нумерует по порядку все комбинации перестановок, то есть присваивает каждой комбинации свой уникальный номер. Из этого номера можно восстановить конкретную комбинацию. Таким образом получается двустороннее соответствие комбинации перестановок и числа от 0 до n!-1. Перестановки 5 из 5 нумеруются от 0 до 119.
В прилагаемом файле пять столбцов со всеми комбинациями перестановок и зелёный столбец, что должно получиться. Формула протягиваемая.
Первое моё решение "в лоб" для комбинации 5 из 5 было 93 символа. Сократил до 86.
Универсальная формула (от 3 из 3 до 9 из 9) тоже 86 символов, только разные диапазоны и константы.
Для обратного преобразования - получения комбинации из номера, универсальной формулы пока не получилось.
Во время решения задачи столкнулся со странным поведением некоторых стандартных функций Excel. Когда вскроюсь, увидите. Думаю, что до следующего понедельника (05.09.16) времени будет достаточно.
[p.s.]Надеюсь, что участников будет больше, чем на прошлых моих задачках.
Возможно, что у кого-то получится не такая строгая последовательность номеров, но будут однозначно номера от 0 до 119, решение засчитается.
Удачи!
К сообщению приложен файл: N_Perest.xls (30.0 Kb)


Программировать проще, чем писать стихи.

Сообщение отредактировал Светлый - Четверг, 25.08.2016, 14:48
 
Ответить
СообщениеВсем доброго дня!
Опять решил подбросить дров в интеллектуальные костры участников МШ.
Когда-то помогал сыну с задачками по комбинаторике и придумал и реализовал алгоритм, который нумерует по порядку все комбинации перестановок, то есть присваивает каждой комбинации свой уникальный номер. Из этого номера можно восстановить конкретную комбинацию. Таким образом получается двустороннее соответствие комбинации перестановок и числа от 0 до n!-1. Перестановки 5 из 5 нумеруются от 0 до 119.
В прилагаемом файле пять столбцов со всеми комбинациями перестановок и зелёный столбец, что должно получиться. Формула протягиваемая.
Первое моё решение "в лоб" для комбинации 5 из 5 было 93 символа. Сократил до 86.
Универсальная формула (от 3 из 3 до 9 из 9) тоже 86 символов, только разные диапазоны и константы.
Для обратного преобразования - получения комбинации из номера, универсальной формулы пока не получилось.
Во время решения задачи столкнулся со странным поведением некоторых стандартных функций Excel. Когда вскроюсь, увидите. Думаю, что до следующего понедельника (05.09.16) времени будет достаточно.
[p.s.]Надеюсь, что участников будет больше, чем на прошлых моих задачках.
Возможно, что у кого-то получится не такая строгая последовательность номеров, но будут однозначно номера от 0 до 119, решение засчитается.
Удачи!

Автор - Светлый
Дата добавления - 25.08.2016 в 13:30
Светлый Дата: Четверг, 25.08.2016, 14:08 | Сообщение № 2
Группа: Друзья
Ранг: Старожил
Сообщений: 1821
Репутация: 506 ±
Замечаний: 0% ±

Excel 2013, 2016
Для обратного преобразования - получения комбинации из номера, универсальной формулы пока не получилось.

Добился универсальной формулы 111 символов с пустой ячейкой перед комбинацией.


Программировать проще, чем писать стихи.
 
Ответить
Сообщение
Для обратного преобразования - получения комбинации из номера, универсальной формулы пока не получилось.

Добился универсальной формулы 111 символов с пустой ячейкой перед комбинацией.

Автор - Светлый
Дата добавления - 25.08.2016 в 14:08
MCH Дата: Четверг, 25.08.2016, 21:22 | Сообщение № 3
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

Компьютера сейчас под рукой нет но решить можно через факториалы.
К воскресенью надеюсь смогу поучаствовать.
Обратное преобразование из номера в перестановку можно сделать
 
Ответить
СообщениеКомпьютера сейчас под рукой нет но решить можно через факториалы.
К воскресенью надеюсь смогу поучаствовать.
Обратное преобразование из номера в перестановку можно сделать

Автор - MCH
Дата добавления - 25.08.2016 в 21:22
MCH Дата: Четверг, 25.08.2016, 21:36 | Сообщение № 4
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

Вот здесь: http://www.excelworld.ru/forum/2-12492-1
Более подробно написано, как получить перестановку по её номеру, возможно поможет для формульной реализации
 
Ответить
СообщениеВот здесь: http://www.excelworld.ru/forum/2-12492-1
Более подробно написано, как получить перестановку по её номеру, возможно поможет для формульной реализации

Автор - MCH
Дата добавления - 25.08.2016 в 21:36
Светлый Дата: Пятница, 26.08.2016, 09:19 | Сообщение № 5
Группа: Друзья
Ранг: Старожил
Сообщений: 1821
Репутация: 506 ±
Замечаний: 0% ±

Excel 2013, 2016
решить можно через факториалы

Действительно, есть позиционная система счисления с факториальным весом позиций. Это близко к заданию.
Обратное преобразование из номера в перестановку можно сделать

Как раз хотел в следующем задании МШ предложить создать формулу генерации перестановок из образца.
Раз уже есть решения, то не буду повторяться. Хотя для соревновательности моё решение 135 символов. А полностью универсальное 216 символов. Надо в первые (одну, две,.. восемь) ячейки вписать тексты или числа, а ниже автоматически показывает все остальные перестановки.


Программировать проще, чем писать стихи.
 
Ответить
Сообщение
решить можно через факториалы

Действительно, есть позиционная система счисления с факториальным весом позиций. Это близко к заданию.
Обратное преобразование из номера в перестановку можно сделать

Как раз хотел в следующем задании МШ предложить создать формулу генерации перестановок из образца.
Раз уже есть решения, то не буду повторяться. Хотя для соревновательности моё решение 135 символов. А полностью универсальное 216 символов. Надо в первые (одну, две,.. восемь) ячейки вписать тексты или числа, а ниже автоматически показывает все остальные перестановки.

Автор - Светлый
Дата добавления - 26.08.2016 в 09:19
Светлый Дата: Пятница, 26.08.2016, 13:12 | Сообщение № 6
Группа: Друзья
Ранг: Старожил
Сообщений: 1821
Репутация: 506 ±
Замечаний: 0% ±

Excel 2013, 2016
Для варианта 5 из 5 с массивными константами получилось 64 символа. Без констант - универсальная 85 символов. Эта формула уже с другими функциями.


Программировать проще, чем писать стихи.
 
Ответить
СообщениеДля варианта 5 из 5 с массивными константами получилось 64 символа. Без констант - универсальная 85 символов. Эта формула уже с другими функциями.

Автор - Светлый
Дата добавления - 26.08.2016 в 13:12
MCH Дата: Воскресенье, 28.08.2016, 00:35 | Сообщение № 7
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

По исходному заданию, вычислить номер перестановки исходя из комбинации
Для варианта 5ти чисел, используя константы - 64 символа, можно написать универсальную, но будет длиннее

UPD:
Есть две разные формулы на 60 и 61 знак (с учетом "=")
 
Ответить
СообщениеПо исходному заданию, вычислить номер перестановки исходя из комбинации
Для варианта 5ти чисел, используя константы - 64 символа, можно написать универсальную, но будет длиннее

UPD:
Есть две разные формулы на 60 и 61 знак (с учетом "=")

Автор - MCH
Дата добавления - 28.08.2016 в 00:35
Светлый Дата: Воскресенье, 28.08.2016, 15:07 | Сообщение № 8
Группа: Друзья
Ранг: Старожил
Сообщений: 1821
Репутация: 506 ±
Замечаний: 0% ±

Excel 2013, 2016
Для варианта 5 из 5 с массивными константами получилось 64 символа.

С подсказкой от MCH сократил до 56 55 символов(если допустить нумерацию в обратном порядке, то 54 символа), а универсальные варианты с разными функциями 74 и 71 70 (69) символов.
Как хорошо, что есть у кого учиться!


Программировать проще, чем писать стихи.

Сообщение отредактировал Светлый - Воскресенье, 28.08.2016, 20:00
 
Ответить
Сообщение
Для варианта 5 из 5 с массивными константами получилось 64 символа.

С подсказкой от MCH сократил до 56 55 символов(если допустить нумерацию в обратном порядке, то 54 символа), а универсальные варианты с разными функциями 74 и 71 70 (69) символов.
Как хорошо, что есть у кого учиться!

Автор - Светлый
Дата добавления - 28.08.2016 в 15:07
krosav4ig Дата: Воскресенье, 28.08.2016, 20:52 | Сообщение № 9
Группа: Друзья
Ранг: Старожил
Сообщений: 2346
Репутация: 989 ±
Замечаний: 0% ±

Excel 2007,2010,2013
нашел я фсе-таки время и силы (ибо в комбинаторике я не силен) для этой задачки
получил формулу номера перестановки 5 из 5 для лексиграфического порядка 97 символов с константами
для антилексиграфического порядка 162 символа с константами
универсальне монстроформулы генерации перестановки m из n по номеру в лексиграфическогм и антилексиграфическом порядке 334 каждая
[p.s.]формулы генерации не мои, пару лет назад бесцеремонно спер формулу у FrankensTeam, сейчас ее немного адаптировал


email:krosav4ig26@gmail.com WMR R207627035142 WMZ Z821145374535 ЯД 410012026478460

Сообщение отредактировал krosav4ig - Воскресенье, 28.08.2016, 21:29
 
Ответить
Сообщениенашел я фсе-таки время и силы (ибо в комбинаторике я не силен) для этой задачки
получил формулу номера перестановки 5 из 5 для лексиграфического порядка 97 символов с константами
для антилексиграфического порядка 162 символа с константами
универсальне монстроформулы генерации перестановки m из n по номеру в лексиграфическогм и антилексиграфическом порядке 334 каждая
[p.s.]формулы генерации не мои, пару лет назад бесцеремонно спер формулу у FrankensTeam, сейчас ее немного адаптировал

Автор - krosav4ig
Дата добавления - 28.08.2016 в 20:52
Светлый Дата: Среда, 31.08.2016, 10:54 | Сообщение № 10
Группа: Друзья
Ранг: Старожил
Сообщений: 1821
Репутация: 506 ±
Замечаний: 0% ±

Excel 2013, 2016
нашел я фсе-таки время и силы

Трое участников - это уже прогресс. Но раньше то 5-7 не было пределом. До понедельника ещё осталось время. Может быть, кто-то ещё присоединится? Что-то не наблюдается азарта в самой интеллектуальной части форумчан.


Программировать проще, чем писать стихи.
 
Ответить
Сообщение
нашел я фсе-таки время и силы

Трое участников - это уже прогресс. Но раньше то 5-7 не было пределом. До понедельника ещё осталось время. Может быть, кто-то ещё присоединится? Что-то не наблюдается азарта в самой интеллектуальной части форумчан.

Автор - Светлый
Дата добавления - 31.08.2016 в 10:54
китин Дата: Среда, 31.08.2016, 11:14 | Сообщение № 11
Группа: Модераторы
Ранг: Экселист
Сообщений: 7011
Репутация: 1073 ±
Замечаний: 0% ±

Excel 2007;2010;2016
Что-то не наблюдается азарта

азарт есть: знаний нет :'(


Не судите очень строго:я пытаюсь научиться
ЯД 41001877306852
 
Ответить
Сообщение
Что-то не наблюдается азарта

азарт есть: знаний нет :'(

Автор - китин
Дата добавления - 31.08.2016 в 11:14
MCH Дата: Среда, 31.08.2016, 12:43 | Сообщение № 12
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

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

Но то, что на форуме есть несколько человек, способных решить подобную задачу, это уже очень хорошо.

PS: Можно предложить следующую подобную задачу на комбинаторику: 5 из 36
по номеру комбинации получить выборку и наоборот по выборке получить порядковый номер.
 
Ответить
СообщениеНа мой взгляд, задача сложная. Здесь необходимы знания в области комбинаторики.
Как минимум, задачу нужно хотя бы решить, найти алгоритм решения, а потом уже смотреть пути снижения размера формул.
Думаю, что проблема возникает как раз с первым (решить саму задачу).

Но то, что на форуме есть несколько человек, способных решить подобную задачу, это уже очень хорошо.

PS: Можно предложить следующую подобную задачу на комбинаторику: 5 из 36
по номеру комбинации получить выборку и наоборот по выборке получить порядковый номер.

Автор - MCH
Дата добавления - 31.08.2016 в 12:43
krosav4ig Дата: Среда, 31.08.2016, 14:00 | Сообщение № 13
Группа: Друзья
Ранг: Старожил
Сообщений: 2346
Репутация: 989 ±
Замечаний: 0% ±

Excel 2007,2010,2013

:'( это ж 36!/31!=45239040 комбинаций
лучше тада ужо 7 из 49 (49!/42!=432938943360 комбинаций) %)


email:krosav4ig26@gmail.com WMR R207627035142 WMZ Z821145374535 ЯД 410012026478460

Сообщение отредактировал krosav4ig - Среда, 31.08.2016, 14:26
 
Ответить
Сообщение
:'( это ж 36!/31!=45239040 комбинаций
лучше тада ужо 7 из 49 (49!/42!=432938943360 комбинаций) %)

Автор - krosav4ig
Дата добавления - 31.08.2016 в 14:00
MCH Дата: Среда, 31.08.2016, 14:07 | Сообщение № 14
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

это ж 36!/31!=45239040 комбинаций

немного не так
ЧИСЛКОМБ(36;5) = 36!/31!/5! = 376992
 
Ответить
Сообщение
это ж 36!/31!=45239040 комбинаций

немного не так
ЧИСЛКОМБ(36;5) = 36!/31!/5! = 376992

Автор - MCH
Дата добавления - 31.08.2016 в 14:07
Светлый Дата: Среда, 31.08.2016, 19:07 | Сообщение № 15
Группа: Друзья
Ранг: Старожил
Сообщений: 1821
Репутация: 506 ±
Замечаний: 0% ±

Excel 2013, 2016
Нарисовал формулу 113 символов и проверил. 45239040 комбинаций. Но среди них есть одинаковые наборы, только в разном порядке. Надо это исключить. Тогда получится 376992. Такую формулу пока не представляю.


Программировать проще, чем писать стихи.
 
Ответить
СообщениеНарисовал формулу 113 символов и проверил. 45239040 комбинаций. Но среди них есть одинаковые наборы, только в разном порядке. Надо это исключить. Тогда получится 376992. Такую формулу пока не представляю.

Автор - Светлый
Дата добавления - 31.08.2016 в 19:07
MCH Дата: Четверг, 01.09.2016, 06:33 | Сообщение № 16
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

Для "спортлото" (5 из 36), по любой комбинации от 1,2,3,4,5 до 32,33,34,35,36, подсчитывает ее номер (от 1 до 376992) как указано в файле
В желтых ячейках указана комбинация, в зеленых ее номер, столбец А пустой, так легче написать формулу.
Формула - 100 знаков
К сообщению приложен файл: 536.xls (28.5 Kb)
 
Ответить
СообщениеДля "спортлото" (5 из 36), по любой комбинации от 1,2,3,4,5 до 32,33,34,35,36, подсчитывает ее номер (от 1 до 376992) как указано в файле
В желтых ячейках указана комбинация, в зеленых ее номер, столбец А пустой, так легче написать формулу.
Формула - 100 знаков

Автор - MCH
Дата добавления - 01.09.2016 в 06:33
Светлый Дата: Четверг, 01.09.2016, 14:13 | Сообщение № 17
Группа: Друзья
Ранг: Старожил
Сообщений: 1821
Репутация: 506 ±
Замечаний: 0% ±

Excel 2013, 2016
Формула - 100 знаков

У меня пока 57 символов, но работает только в 2007 и выше.
При сравнении проявилась ошибка округления, пришлось увеличивать до 63 символов.
В любом офисе формулы 69 с погрешностью и 75 символов целочисленная нумерация.


Программировать проще, чем писать стихи.

Сообщение отредактировал Светлый - Четверг, 01.09.2016, 18:44
 
Ответить
Сообщение
Формула - 100 знаков

У меня пока 57 символов, но работает только в 2007 и выше.
При сравнении проявилась ошибка округления, пришлось увеличивать до 63 символов.
В любом офисе формулы 69 с погрешностью и 75 символов целочисленная нумерация.

Автор - Светлый
Дата добавления - 01.09.2016 в 14:13
buchlotnik Дата: Воскресенье, 04.09.2016, 14:13 | Сообщение № 18
Группа: Заблокированные
Ранг: Участник клуба
Сообщений: 3442
Репутация: 929 ±
Замечаний: 20% ±

2010, 2013, 2016 RUS / ENG
дошли руки наконец-то: исходная задача у меня 55 символов 51 символ (массивка с константами)


Сообщение отредактировал buchlotnik - Воскресенье, 04.09.2016, 14:16
 
Ответить
Сообщениедошли руки наконец-то: исходная задача у меня 55 символов 51 символ (массивка с константами)

Автор - buchlotnik
Дата добавления - 04.09.2016 в 14:13
Светлый Дата: Понедельник, 05.09.2016, 08:16 | Сообщение № 19
Группа: Друзья
Ранг: Старожил
Сообщений: 1821
Репутация: 506 ±
Замечаний: 0% ±

Excel 2013, 2016
Хорошо, что времени было достаточно. Будет на что посмотреть и оценить.
Вскрываюсь по своей задаче:
Код
=СУММ(СЧЁТЕСЛИ(СМЕЩ(E1;;;;СТОЛБЕЦ(A:D)-6);"<"&A1:D1)*ФАКТР(5-СТОЛБЕЦ(A:D)))

Код
=152-СУММ(РАНГ(A1:D1;СМЕЩ(E1;;;;СТОЛБЕЦ(A:D)-6))*ФАКТР(5-СТОЛБЕЦ(A:D)))

Код
=152-СУММ(РАНГ(A1:D1;СМЕЩ(E1;;;;-{5;4;3;2}))*{24;6;2;1})

И по встречной задаче "5 из 36" от MCH:
Код
=ОТБР(376956-СУММ(ЕСЛИ(36-B1:E1>{4;3;2;1};ЧИСЛКОМБ(36-B1:E1;{5;4;3;2})))+F1)

Код
=376956-СУММ(ЕСЛИ(36-B1:E1>{4;3;2;1};ЧИСЛКОМБ(36-B1:E1;{5;4;3;2})))+F1

Код
=ОТБР(376956-СУММ(ЕСЛИОШИБКА(ЧИСЛКОМБ(36-B1:E1;{5;4;3;2});))+F1)


Программировать проще, чем писать стихи.
 
Ответить
СообщениеХорошо, что времени было достаточно. Будет на что посмотреть и оценить.
Вскрываюсь по своей задаче:
Код
=СУММ(СЧЁТЕСЛИ(СМЕЩ(E1;;;;СТОЛБЕЦ(A:D)-6);"<"&A1:D1)*ФАКТР(5-СТОЛБЕЦ(A:D)))

Код
=152-СУММ(РАНГ(A1:D1;СМЕЩ(E1;;;;СТОЛБЕЦ(A:D)-6))*ФАКТР(5-СТОЛБЕЦ(A:D)))

Код
=152-СУММ(РАНГ(A1:D1;СМЕЩ(E1;;;;-{5;4;3;2}))*{24;6;2;1})

И по встречной задаче "5 из 36" от MCH:
Код
=ОТБР(376956-СУММ(ЕСЛИ(36-B1:E1>{4;3;2;1};ЧИСЛКОМБ(36-B1:E1;{5;4;3;2})))+F1)

Код
=376956-СУММ(ЕСЛИ(36-B1:E1>{4;3;2;1};ЧИСЛКОМБ(36-B1:E1;{5;4;3;2})))+F1

Код
=ОТБР(376956-СУММ(ЕСЛИОШИБКА(ЧИСЛКОМБ(36-B1:E1;{5;4;3;2});))+F1)

Автор - Светлый
Дата добавления - 05.09.2016 в 08:16
buchlotnik Дата: Понедельник, 05.09.2016, 08:57 | Сообщение № 20
Группа: Заблокированные
Ранг: Участник клуба
Сообщений: 3442
Репутация: 929 ±
Замечаний: 20% ±

2010, 2013, 2016 RUS / ENG
в исходную задачу я как-то совсем по-другому зашёл :D
Код
=СУММ(24*(B1>C1:F1);6*(C1>D1:F1);2*(D1>E1:F1);E1>F1)
К сообщению приложен файл: N_Perest-1-.xls (55.0 Kb)


Сообщение отредактировал buchlotnik - Понедельник, 05.09.2016, 09:09
 
Ответить
Сообщениев исходную задачу я как-то совсем по-другому зашёл :D
Код
=СУММ(24*(B1>C1:F1);6*(C1>D1:F1);2*(D1>E1:F1);E1>F1)

Автор - buchlotnik
Дата добавления - 05.09.2016 в 08:57
Мир MS Excel » Работа и общение » Мозговой штурм » Номер комбинации перестановки
  • Страница 1 из 2
  • 1
  • 2
  • »
Поиск:

Яндекс.Метрика Яндекс цитирования
© 2010-2024 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!