powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / найти нужное сочетание без повторений
43 сообщений из 43, показаны все 2 страниц
найти нужное сочетание без повторений
    #36602320
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Приветствую всех форумчан, встал вопрос, а как найти необходимое сочетание 8 столбцов из 24 столбцов?
необходимое - тк есть условие, в сумме построчно - четные числа (или 0 mod 2) - но это дело 10е

число различных сочетаний без повторений n!/(n-k)!k! что в нашем случае 735471 шт)

проблема - не знаю как подступиться, т.е. как выбирать 8 различных столбцов для сравнения, чтобы они не повторялись
подскажите идею, спасибо
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36602350
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А в чем проблема? Считаете, что перебор будет слишком долгим?
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36602871
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603043
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
за ссылку спасибо)

ну в данном конкретном случае - думаю 70 ывриантов как раз плюнуть для экселя, а вот, если будет на пару порядков больше - тут уже надо думать)
если есть какой совет - может сталкивались с таким - для больших чисел m и n - поделитесь, спасибо)
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603049
Фотография Konst_One
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
сначала посмотрите в хэлпе экселя про ограничения кол-ва столбцов и рядов в листе
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603070
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Konst_Oneсначала посмотрите в хэлпе экселя про ограничения кол-ва столбцов и рядов в листе

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

Я думаю, тут надо думать в сторону хэширования...
К примеру, четные значения не интересуют вообще, они всегда в сумме дадут четное...
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603328
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
стесняюсь спросить,а при чем здесь ограничение по столбцам и строкам?
суть вот какая:
есть числа 1...24 - номера столбцов
пытаюсь найти алгоритм (п оссылке выше что-то он мутноватый какой-то) - как перебрать все сочетания без повторений по 8 столбцов,
а внутри конкретного сочетания уже проверять условие - это дело тридцатое и как его реализовать я знаю

единственная загвоздка как раз в алгоритме, тк на этом этапе массив не огромен и это делается в excele для наглядности (мысль была, что буфер переполнится, но потом отпала)
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603333
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Shocker.Pro[quot Konst_One]К примеру, четные значения не интересуют вообще, они всегда в сумме дадут четное...
не совсем так) у меня матрица из 0 и 1, про четные нечентные я просто так написал, для абстракции
но опять же на тему условия заморачиваться даже не стоит - важно перебрать все сочетания
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603349
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rongermeкак перебрать все сочетания без повторений по 8 столбцов

Первое, что пришло в голову - брутфорс
- устроить цикл от 1 до 2^24
- переводить число в бинарное представление, посчитать количество единиц
- если 8 - значит это маска нужных нам столбцов (без повторений)
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603507
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Shocker.Prorongermeкак перебрать все сочетания без повторений по 8 столбцов

Первое, что пришло в голову - брутфорс
- устроить цикл от 1 до 2^24
- переводить число в бинарное представление, посчитать количество единиц
- если 8 - значит это маска нужных нам столбцов (без повторений)


а почему 8? ведь в каждом представлении может быть несколько 1?
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603527
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rongermeа почему 8? ведь в каждом представлении может быть несколько 1?

потому что вы просили, сочетание 8 столбцов.
Если вам нужно расширенное сочетание (от 1 до 8 столбцов), то соответственно и надо подсчитывать количество единиц от 1 до 8

(просто не помню уже вычисление сочетаний и не могу сделать реверс-инжиниринг формулы n!/(n-k)!k!)

Я не понял, что такое "представление" в вашей формулировке, поэтому, возможно, дал неточный ответ.
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603539
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
000000000000000000000001 - не подходит
000000000000000000000010 - не подходит
000000000000000000000011 - не подходит
000000000000000000000100 - не подходит
...
000000000000000011111110 - не подходит
000000000000000011111111 - подходит
000000000000000100000000 - не подходит
...
000010010111010000100000 - не подходит
000010010111010000100001 - подходит
000010010111010000100010 - подходит
000010010111010000100011 - не подходит
....

и т.п.
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603560
Фотография Игорь Горбонос
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
> Автор: Shocker.Pro
> 000010010111010000100010 - подходит
> 000010010111010000100011 - не подходит


Здается мне это похоже на степени двойки, начиная с определенного числа - 255

Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603569
Фотография Konst_One
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
я вообще потерял нить рассуждений автора. о каких совпадениях идёт речь? он решил в лоб сравнивать биты через посимвольное сравнение как строки?
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603576
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603581
Фотография Konst_One
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
достали эти студенты сегодня. я ещё им должен комбинаторику вспоминать 20-летней давности
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603587
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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 и тп
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603588
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Konst_Oneдостали эти студенты сегодня. я ещё им должен комбинаторику вспоминать 20-летней давности

Да ладно. Тут хоть есть где мозгами пошевелить.
Хотя пока более интересного способа поиска сочетаний я пока не придумал.
А что сказал Игорь вообще не понял.
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603596
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603622
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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?
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603635
Фотография Konst_One
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вам для чего это нужно?
какова реальная задача и что вы хотите получить?
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603636
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rongermeтак ведь мы получим только числа кратные 8?

Это еще почему?

rongermeкак вашим методом получить последовательность 1,2,5,6,8,20,21,24?

очередное число, на которое вы наткнетесь будет
110011010000000000011001 (биты пронумеровваны справа налево)

то есть единички стоят в позициях 1,2,5,6,8,20,21,24 - это и есть подходящая маска.
Десятичный эквивалент этого числа - 13434905
то есть это сочетание встретится на 13434905-й итерации цикла
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603638
Фотография Игорь Горбонос
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
> Автор: Shocker.Pro
> А что сказал Игорь вообще не понял.

Я сказал, что числа меньше 255 проверять нет смысла, т.к. первые восемь едениц в двоичном представлении получаются у
числа 255. т.е. 2^8-1. Дальше нужно попробовать получить формулу по которой можно получать эти цифры. Или понять
алгоритм эффективной проверки

> Да ладно. Тут хоть есть где мозгами пошевелить.
> Хотя пока более интересного способа поиска сочетаний я пока не придумал.



Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603647
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Shocker.Pro110011010000000000011001 (биты пронумеровваны справа налево)

ой, в данном случае слева направо, но работать тоже будет
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603655
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Konst_Oneвам для чего это нужно?
какова реальная задача и что вы хотите получить?
мне нужно дешифровать сообщение, если в общем
более точно: матрицу 16х24 (из 0 и 1) надо разбить на 3 блока (1 блок - матрица 16х8), известно, что в каждая строка блока в сумме доет 0 mod 2
так вот, я хочу наложить это условие на каждое сочетание (дргими словами, на каждый возможный вариант группы из 8 столбцов, где каждый столбец не повторяется в этой группе)
чтобы это сделать, необходимо пробежать по всем сочетаниям - для этого и спрашиваю алгоритм
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603658
Фотография Konst_One
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
http://msdn.microsoft.com/ru-ru/library/csw1x2a6(VS.90).aspx

оператор XOR
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603662
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Игорь Горбоносчисла 255. т.е. 2^8-1. Дальше нужно попробовать получить формулу по которой можно получать эти цифры. Или понять
алгоритм эффективной проверки

а если не 8 а n?
то есть по хорошему надо начинать не сначала (2^n) и идти не до конца (ибо когда в старших разрядах появится n единичек, дальнейший цикл потеряет смысл)

Но это уже детали.
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603668
Фотография Konst_One
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VB 6.0 не очень удачно вы выбрали. для таких вещей вам лучше C/C++ использовать
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603684
Фотография Игорь Горбонос
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
> Автор: Shocker.Pro
> а если не 8 а n?

Не понял

> то есть по хорошему надо начинать не сначала (2^n) и идти не до конца (ибо когда в старших разрядах появится n
> единичек, дальнейший цикл потеряет смысл)

Правильно, последнее максимальное число - 16711680

> Но это уже детали.

Это точно :)

Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603702
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Konst_OneVB 6.0 не очень удачно вы выбрали. для таких вещей вам лучше C/C++ использовать
в общем случае так и планируется)
в экселе только потому, что начал вручную разбирать весь алгоритм в клеточках)))
(*это не важно*)

но алгоритм то все-равно пригодится)))
спасибо!
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603707
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Игорь Горбонос
> Автор: Shocker.Pro
> а если не 8 а n?

Не понял

Допустим у нас X танков. Хотя нет, X - мало, пусть будет Y танков...

Автор оговорился, что число может меняться.
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603736
Фотография Konst_One
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rongermeKonst_OneVB 6.0 не очень удачно вы выбрали. для таких вещей вам лучше C/C++ использовать
в общем случае так и планируется)
в экселе только потому, что начал вручную разбирать весь алгоритм в клеточках)))
(*это не важно*)

но алгоритм то все-равно пригодится)))
спасибо!

это я к тому, что бэйсик не оперирует двоичным представлением числа. у него мало средств для работы с таким представлением. побитные операции лучше реализовывать в языках типа C/Java и тп, т.к. там это делать проще, компактней и наглядней.
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603750
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Konst_Onehttp://msdn.microsoft.com/ru-ru/library/csw1x2a6(VS.90).aspx

оператор XOR
я вам о пирожках, а вы мне о котлетах )
знаю я XOR))
я же говорил, что как реализовать условие сейчас не важно -я знаю,
важно было перебрать все последовательности, чтоб не пропустить ничего
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603759
Фотография Konst_One
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А я вам толкую, что матричное исчисление в таком применении как вы хотите - это плохо. оперируйте байтами и 32-х 64-х словами
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603761
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rongermeважно было перебрать все последовательности, чтоб не пропустить ничего

Так это...
разобрались в моем алгоритме?
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603807
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Shocker.Prorongermeважно было перебрать все последовательности, чтоб не пропустить ничего

Так это...
разобрались в моем алгоритме?
вроде бы
контрольный выстрел:
начиная с 100000000000000000000000 с прибавлением по биту двигаемся
и когда сумма единичек равна 8, позиции, где стоят 1 - это и есть номера столбцов
все такие столбцы - мои клиенты, так?
ограничиваем сверху цикл 2^24
не напутал?
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603831
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну можно и так :)
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36603989
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.
Public Function Combination(ByVal m As Long, ByVal n As Long) As Long
 Dim x() As Long
 ReDim x( 1  To m) As Long  'Индексы
 Dim i As Long, k As Long 'Позиции
 Dim s As String          'Комбинация в строковом виде
 Dim l As Long            'Счётчик комбинаций
 
 'Необязательная инициализация
 'For i = 1 To m
 '   x(i) = i
 'Next i
 
 k =  1  '= m, если была проведена закомментированная выше инициализация
 Do
    If x(k) < n - m + k Then
       x(k) = x(k) +  1 
       For i = k +  1  To m
          x(i) = x(k) + (i - k)
       Next i
       k = m
    
       'Здесь комбинация готова к выдаче. Не печатаем её, хотя можем это
       'сделать, раскомментировав код печати ниже. Просто увеличиваем счётчик
       'комбинаций.
       l = l +  1 
'       'Печать комбинации
'       s = x(1)
'       For i = 2 To m
'          s = s & "," & x(i)
'       Next i
'       Debug.Print l, s
     
    Else
       If k <=  1  Then Exit Do
       k = k -  1 
    End If
 Loop
 Combination = l
End Function
Кстати, что там с временем выполнения?
t0=Timer:?Combination(8,24),Timer-t0
735471 0,40625
Четыре десятых секунды на моей дохлой тачке... Юзер определённо заколе устанет ждать.
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36604386
Фотография Игорь Горбонос
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Shocker.ProДопустим у нас X танков. Хотя нет, X - мало, пусть будет Y танков...

Ну так бы сразу и сказал

Эх, я когда-то рисовал различные фракталы, особенно долго просидел со скатертью Улама У меня должен быть ексельный файл в котором я выводил формулы вычисления координат для числа :)

Как давно это было , а кажется совсем недавно
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36604462
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Игорь ГорбоносНу так бы сразу и сказал

Это скорей к "Первый результат в Гугле" высказывание.
Ибо алгоритм-то рабочий, хоть и "мутный" по выражению ТС, а мы тут мастурбировали две страницы (извиняюсь). Мне стыдно, что я не гожусь на олимпиаду для школьников.
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36604468
Фотография Игорь Горбонос
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
> Автор: Shocker.Pro
> Мне стыдно, что я не гожусь на олимпиаду для школьников.

Если интересно, возьми для себя и порисуй фракталы. Мне очень понравилось.
Правда я это делал на С++, но не вижу препятствий сделать это на VB


Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36604501
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Первый результат в Гуглеrongermeп оссылке выше что-то он мутноватый какой-тоПпц, приплыли! Этот, с позволения сказать, алгоритм, придумывают и реализуют 12-13-летние пацаны на школьной олимпиаде по программированию.
...
Рейтинг: 0 / 0
найти нужное сочетание без повторений
    #36604507
rongerme
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
забыл текст вставить )
спасибо, просто на работе почему - то я его коряво прочитал - дома уже все понятно было))))
а сейчас посмотрел, вы еще и реализовали его - спасибо большое)

стыдно мене ))
...
Рейтинг: 0 / 0
43 сообщений из 43, показаны все 2 страниц
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / найти нужное сочетание без повторений
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]