Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Приветствую всех форумчан, встал вопрос, а как найти необходимое сочетание 8 столбцов из 24 столбцов? необходимое - тк есть условие, в сумме построчно - четные числа (или 0 mod 2) - но это дело 10е число различных сочетаний без повторений n!/(n-k)!k! что в нашем случае 735471 шт) проблема - не знаю как подступиться, т.е. как выбирать 8 различных столбцов для сравнения, чтобы они не повторялись подскажите идею, спасибо ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 10:47 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
А в чем проблема? Считаете, что перебор будет слишком долгим? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 10:56 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 13:36 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
за ссылку спасибо) ну в данном конкретном случае - думаю 70 ывриантов как раз плюнуть для экселя, а вот, если будет на пару порядков больше - тут уже надо думать) если есть какой совет - может сталкивались с таким - для больших чисел m и n - поделитесь, спасибо) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 14:26 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
сначала посмотрите в хэлпе экселя про ограничения кол-ва столбцов и рядов в листе ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 14:27 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Konst_Oneсначала посмотрите в хэлпе экселя про ограничения кол-ва столбцов и рядов в листе Ну тут время будет расти в геометрической прогрессии и вряд ли упремся в ограничение экселя раньше, чем в терпение юзера. Я думаю, тут надо думать в сторону хэширования... К примеру, четные значения не интересуют вообще, они всегда в сумме дадут четное... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 14:33 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
стесняюсь спросить,а при чем здесь ограничение по столбцам и строкам? суть вот какая: есть числа 1...24 - номера столбцов пытаюсь найти алгоритм (п оссылке выше что-то он мутноватый какой-то) - как перебрать все сочетания без повторений по 8 столбцов, а внутри конкретного сочетания уже проверять условие - это дело тридцатое и как его реализовать я знаю единственная загвоздка как раз в алгоритме, тк на этом этапе массив не огромен и это делается в excele для наглядности (мысль была, что буфер переполнится, но потом отпала) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 15:50 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Shocker.Pro[quot Konst_One]К примеру, четные значения не интересуют вообще, они всегда в сумме дадут четное... не совсем так) у меня матрица из 0 и 1, про четные нечентные я просто так написал, для абстракции но опять же на тему условия заморачиваться даже не стоит - важно перебрать все сочетания ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 15:52 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
rongermeкак перебрать все сочетания без повторений по 8 столбцов Первое, что пришло в голову - брутфорс - устроить цикл от 1 до 2^24 - переводить число в бинарное представление, посчитать количество единиц - если 8 - значит это маска нужных нам столбцов (без повторений) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 15:55 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Shocker.Prorongermeкак перебрать все сочетания без повторений по 8 столбцов Первое, что пришло в голову - брутфорс - устроить цикл от 1 до 2^24 - переводить число в бинарное представление, посчитать количество единиц - если 8 - значит это маска нужных нам столбцов (без повторений) а почему 8? ведь в каждом представлении может быть несколько 1? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 16:38 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
rongermeа почему 8? ведь в каждом представлении может быть несколько 1? потому что вы просили, сочетание 8 столбцов. Если вам нужно расширенное сочетание (от 1 до 8 столбцов), то соответственно и надо подсчитывать количество единиц от 1 до 8 (просто не помню уже вычисление сочетаний и не могу сделать реверс-инжиниринг формулы n!/(n-k)!k!) Я не понял, что такое "представление" в вашей формулировке, поэтому, возможно, дал неточный ответ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 16:43 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
000000000000000000000001 - не подходит 000000000000000000000010 - не подходит 000000000000000000000011 - не подходит 000000000000000000000100 - не подходит ... 000000000000000011111110 - не подходит 000000000000000011111111 - подходит 000000000000000100000000 - не подходит ... 000010010111010000100000 - не подходит 000010010111010000100001 - подходит 000010010111010000100010 - подходит 000010010111010000100011 - не подходит .... и т.п. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 16:46 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
> Автор: Shocker.Pro > 000010010111010000100010 - подходит > 000010010111010000100011 - не подходит Здается мне это похоже на степени двойки, начиная с определенного числа - 255 Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 16:53 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
я вообще потерял нить рассуждений автора. о каких совпадениях идёт речь? он решил в лоб сравнивать биты через посимвольное сравнение как строки? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 16:56 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Konst_Oneя вообще потерял нить рассуждений автора. о каких совпадениях идёт речь? он решил в лоб сравнивать биты через посимвольное сравнение как строки? http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 16:58 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
достали эти студенты сегодня. я ещё им должен комбинаторику вспоминать 20-летней давности ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 16:59 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Shocker.Pro потому что вы просили, сочетание 8 столбцов. Если вам нужно расширенное сочетание (от 1 до 8 столбцов), то соответственно и надо подсчитывать количество единиц от 1 до 8 (просто не помню уже вычисление сочетаний и не могу сделать реверс-инжиниринг формулы n!/(n-k)!k!) Я не понял, что такое "представление" в вашей формулировке, поэтому, возможно, дал неточный ответ. представление в моем понимании это 1 - 00000001, 2 - 00000010 и тп вы это же имели в виду? а можно на пальцах, а то, не могу понять, какоа алгоритм (хотя бы первые шаги) вот есть числа 1...24 перевели их в двоичное представление, а дальше что? нужно получить последовательности типа 1,2,3,4,5,6,7,8 или 1,10,2,3,4,5,6,7 и тп ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:01 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Konst_Oneдостали эти студенты сегодня. я ещё им должен комбинаторику вспоминать 20-летней давности Да ладно. Тут хоть есть где мозгами пошевелить. Хотя пока более интересного способа поиска сочетаний я пока не придумал. А что сказал Игорь вообще не понял. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:02 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
rongermeвот есть числа 1...24 перевели их в двоичное представление, а дальше что? нужно получить последовательности типа 1,2,3,4,5,6,7,8 или 1,10,2,3,4,5,6,7 и тп не 1-24, а 1-16777216 пример я привел тут. Каждый бит двоичного числа соответствует вашему столбцу №1...24 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:05 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Konst_Oneдостали эти студенты сегодня. я ещё им должен комбинаторику вспоминать 20-летней давности за студента спасибо) польстили Shocker.Prorongermeвот есть числа 1...24 перевели их в двоичное представление, а дальше что? нужно получить последовательности типа 1,2,3,4,5,6,7,8 или 1,10,2,3,4,5,6,7 и тп не 1-24, а 1-16777216 пример я привел тут. Каждый бит двоичного числа соответствует вашему столбцу №1...24 так ведь мы получим только числа кратные 8? а нам ведь надо последовательность как вашим методом получить последовательность 1,2,5,6,8,20,21,24? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:12 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
вам для чего это нужно? какова реальная задача и что вы хотите получить? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:15 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
rongermeтак ведь мы получим только числа кратные 8? Это еще почему? rongermeкак вашим методом получить последовательность 1,2,5,6,8,20,21,24? очередное число, на которое вы наткнетесь будет 110011010000000000011001 (биты пронумеровваны справа налево) то есть единички стоят в позициях 1,2,5,6,8,20,21,24 - это и есть подходящая маска. Десятичный эквивалент этого числа - 13434905 то есть это сочетание встретится на 13434905-й итерации цикла ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:15 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
> Автор: Shocker.Pro > А что сказал Игорь вообще не понял. Я сказал, что числа меньше 255 проверять нет смысла, т.к. первые восемь едениц в двоичном представлении получаются у числа 255. т.е. 2^8-1. Дальше нужно попробовать получить формулу по которой можно получать эти цифры. Или понять алгоритм эффективной проверки > Да ладно. Тут хоть есть где мозгами пошевелить. > Хотя пока более интересного способа поиска сочетаний я пока не придумал. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:15 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Shocker.Pro110011010000000000011001 (биты пронумеровваны справа налево) ой, в данном случае слева направо, но работать тоже будет ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:17 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Konst_Oneвам для чего это нужно? какова реальная задача и что вы хотите получить? мне нужно дешифровать сообщение, если в общем более точно: матрицу 16х24 (из 0 и 1) надо разбить на 3 блока (1 блок - матрица 16х8), известно, что в каждая строка блока в сумме доет 0 mod 2 так вот, я хочу наложить это условие на каждое сочетание (дргими словами, на каждый возможный вариант группы из 8 столбцов, где каждый столбец не повторяется в этой группе) чтобы это сделать, необходимо пробежать по всем сочетаниям - для этого и спрашиваю алгоритм ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:19 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
http://msdn.microsoft.com/ru-ru/library/csw1x2a6(VS.90).aspx оператор XOR ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:19 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Игорь Горбоносчисла 255. т.е. 2^8-1. Дальше нужно попробовать получить формулу по которой можно получать эти цифры. Или понять алгоритм эффективной проверки а если не 8 а n? то есть по хорошему надо начинать не сначала (2^n) и идти не до конца (ибо когда в старших разрядах появится n единичек, дальнейший цикл потеряет смысл) Но это уже детали. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:20 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
VB 6.0 не очень удачно вы выбрали. для таких вещей вам лучше C/C++ использовать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:20 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
> Автор: Shocker.Pro > а если не 8 а n? Не понял > то есть по хорошему надо начинать не сначала (2^n) и идти не до конца (ибо когда в старших разрядах появится n > единичек, дальнейший цикл потеряет смысл) Правильно, последнее максимальное число - 16711680 > Но это уже детали. Это точно :) Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:24 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Konst_OneVB 6.0 не очень удачно вы выбрали. для таких вещей вам лучше C/C++ использовать в общем случае так и планируется) в экселе только потому, что начал вручную разбирать весь алгоритм в клеточках))) (*это не важно*) но алгоритм то все-равно пригодится))) спасибо! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:29 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Игорь Горбонос > Автор: Shocker.Pro > а если не 8 а n? Не понял Допустим у нас X танков. Хотя нет, X - мало, пусть будет Y танков... Автор оговорился, что число может меняться. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:30 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
rongermeKonst_OneVB 6.0 не очень удачно вы выбрали. для таких вещей вам лучше C/C++ использовать в общем случае так и планируется) в экселе только потому, что начал вручную разбирать весь алгоритм в клеточках))) (*это не важно*) но алгоритм то все-равно пригодится))) спасибо! это я к тому, что бэйсик не оперирует двоичным представлением числа. у него мало средств для работы с таким представлением. побитные операции лучше реализовывать в языках типа C/Java и тп, т.к. там это делать проще, компактней и наглядней. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:34 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Konst_Onehttp://msdn.microsoft.com/ru-ru/library/csw1x2a6(VS.90).aspx оператор XOR я вам о пирожках, а вы мне о котлетах ) знаю я XOR)) я же говорил, что как реализовать условие сейчас не важно -я знаю, важно было перебрать все последовательности, чтоб не пропустить ничего ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:36 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
А я вам толкую, что матричное исчисление в таком применении как вы хотите - это плохо. оперируйте байтами и 32-х 64-х словами ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:38 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
rongermeважно было перебрать все последовательности, чтоб не пропустить ничего Так это... разобрались в моем алгоритме? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:38 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Shocker.Prorongermeважно было перебрать все последовательности, чтоб не пропустить ничего Так это... разобрались в моем алгоритме? вроде бы контрольный выстрел: начиная с 100000000000000000000000 с прибавлением по биту двигаемся и когда сумма единичек равна 8, позиции, где стоят 1 - это и есть номера столбцов все такие столбцы - мои клиенты, так? ограничиваем сверху цикл 2^24 не напутал? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:47 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Ну можно и так :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 17:58 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
rongermeп оссылке выше что-то он мутноватый какой-тоПпц, приплыли! Этот, с позволения сказать, алгоритм, придумывают и реализуют 12-13-летние пацаны на школьной олимпиаде по программированию. Перевожу с русского на васик почти дословно, без мелочных оптимизаций: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. t0=Timer:?Combination(8,24),Timer-t0 735471 0,40625 Четыре десятых секунды на моей дохлой тачке... Юзер определённо заколе устанет ждать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.04.2010, 19:22 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Shocker.ProДопустим у нас X танков. Хотя нет, X - мало, пусть будет Y танков... Ну так бы сразу и сказал Эх, я когда-то рисовал различные фракталы, особенно долго просидел со скатертью Улама У меня должен быть ексельный файл в котором я выводил формулы вычисления координат для числа :) Как давно это было , а кажется совсем недавно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.04.2010, 05:04 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Игорь ГорбоносНу так бы сразу и сказал Это скорей к "Первый результат в Гугле" высказывание. Ибо алгоритм-то рабочий, хоть и "мутный" по выражению ТС, а мы тут мастурбировали две страницы (извиняюсь). Мне стыдно, что я не гожусь на олимпиаду для школьников. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.04.2010, 09:10 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
> Автор: Shocker.Pro > Мне стыдно, что я не гожусь на олимпиаду для школьников. Если интересно, возьми для себя и порисуй фракталы. Мне очень понравилось. Правда я это делал на С++, но не вижу препятствий сделать это на VB Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.04.2010, 09:19 |
|
||
|
найти нужное сочетание без повторений
|
|||
|---|---|---|---|
|
#18+
Первый результат в Гуглеrongermeп оссылке выше что-то он мутноватый какой-тоПпц, приплыли! Этот, с позволения сказать, алгоритм, придумывают и реализуют 12-13-летние пацаны на школьной олимпиаде по программированию. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.04.2010, 09:53 |
|
||
|
|

start [/forum/topic.php?all=1&fid=60&tid=2159864]: |
0ms |
get settings: |
9ms |
get forum list: |
14ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
51ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
69ms |
get tp. blocked users: |
1ms |
| others: | 247ms |
| total: | 410ms |

| 0 / 0 |
