powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Комбинации
11 сообщений из 11, страница 1 из 1
Комбинации
    #32577481
arseny
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Как мне получить массив комбинаций с семью цифрами из 70?
Пример (4 из 6): 123456
1234
1235
1236
1245
1246
1256
1345
1346
1356
1456
2345
2346
2356
2456
3456
Рекурсией лучше всего бы наверное...
Есть у кого-нибудь может уже готовые проекты?
p i l l s b u r y
...
Рейтинг: 0 / 0
Комбинации
    #32577515
Hibernate
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну вот, навскидку:
Код: 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.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
Private Function GenerateFullCombination(NumberNumber As Integer, BallsNumber As Integer) () as integer
   'NumberNumber - количество возможных номеров
 
   'BallsNumber - количество номеров в одной комбинации
 

  Dim i As Long
  Dim N As Long
  Dim j As Long
  Dim rez() As Integer
  Dim SysRez As ctSystem
  Dim m As Long
  Dim p() As Long
  Dim p_max() As Long
  Dim nn As Long
  

  N = MeFaktorial(NumberNumber - BallsNumber +  1 , NumberNumber) / Faktorial(BallsNumber)
  
  ReDim rez( 1  To BallsNumber,  1  To N)
  ReDim p( 1  To BallsNumber)
  ReDim p_max( 1  To BallsNumber)
  
  For j =  1  To BallsNumber
    rez(j,  1 ) = j
    p(j) = j
    p_max(j) = NumberNumber - (BallsNumber - j)
  Next j
   
  Dim a As Long
  Dim k As Long

  For i =  2  To N
      k = BallsNumber
      a = rez(k, i -  1 ) +  1 
      While (a > p_max(k)) And (k >  0 )
        k = k -  1 
        a = rez(k, i -  1 ) +  1 
      Wend
      For j =  1  To k -  1 
        rez(j, i) = rez(j, i -  1 )
      Next j
      rez(k, i) = rez(k, i -  1 ) +  1 
      For j = k +  1  To BallsNumber
        rez(j, i) = rez(j -  1 , i) +  1 
      Next j
  Next i
  GenerateFullCombination = rez
  
End Sub

Public Function Faktorial(N As Integer) As Long
  If N =  0  Then
    Faktorial =  1 
  Else
    Faktorial = N * Faktorial(N -  1 )
  End If
End Function

Public Function MeFaktorial(N As Integer, m As Integer) As Long
   'n - стартовый номер
 
   'm - конечный номер
 
  Dim i As Long
  MeFaktorial =  1 
  For i = N To m
    MeFaktorial = MeFaktorial * i
  Next i
End Function


...
Рейтинг: 0 / 0
Комбинации
    #32578435
arseny
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо!
Работает, но с одним " но ".
Если даю задачу перебрать 7 из 70 , то вариантов 'N' выходит миллиард с "небольшим". И массив басик не даёт с таким размером:
ReDim rez(1 To BallsNumber, 1 To N) - ошибка вылетает, где 'N' больше миллиарда . :)
Можно что-то сделать? И в каких рамках такие ограничения?
Спасибки.
p i l l s b u r y
...
Рейтинг: 0 / 0
Комбинации
    #32578519
Фотография ulis
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Перебор - это принципиально неверный путь. Нужно открыть учебник по комбинаторике и найти соответствующую формулу
...
Рейтинг: 0 / 0
Комбинации
    #32578645
Фотография Victosha
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ограничения самые естественные - вин32 процесс не может адресовать более 4 гигабайт виртуальной памяти.

в твоем случае:
число комбинаций - 1 198 774 720
длина целевого массива в байтах - 7*2*1198774720= 16 782 846 080
(то есть больше 15 гигабайт, если я считать не разучился окончательно )

что делать - пожалуй, функцию (в классе) делать, которая по индексу (номеру получившейся комбинации) вычисляет и возвращает комбинацию.
В такой класс можно итератор добавить, который будет GetNextCombination возвращать.
...
Рейтинг: 0 / 0
Комбинации
    #32578827
Шогал
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
M!/((M-N)!N!) , где M - большее из чисел, а N - меньшее
Только не забудьте формулу сократить. У нас на одном чемпе была похожая задача - в итоге те кто сокращали - решили, те кто не сокращали - получили переполнение на подном из тестов.

SHOGAL
...
Рейтинг: 0 / 0
Комбинации
    #32580451
Hibernate
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ШогалM!/((M-N)!N!) , где M - большее из чисел, а N - меньшее
Только не забудьте формулу сократить
так в моем примере функция
Public Function MeFaktorial(N As Integer, m As Integer) As Long
и есть результат сокращения. :-)

По поводу вычисления - хорошая мысль автору вопроса. И переделать данную функцию наверное нетрудно будет но это уже для домашнего задания :-)
...
Рейтинг: 0 / 0
Комбинации
    #32582153
arseny
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Так в том то и дело, что проблема не в вычислении количества комбинаций, а в резервировании массива на это ужасно огромное количество комбинаций.
Вот...
p i l l s b u r y
...
Рейтинг: 0 / 0
Комбинации
    #32582185
(c)VIG
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну так создай столько массивов , сколько нужно и заполняй их по очереди.В чем проблема ?
P.S C Миф'аль ha Паис в азартные игры играешь ?
...
Рейтинг: 0 / 0
Комбинации
    #32582189
arseny
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Что-то вроде...
Хочу доказать себе, что с ними не поиграешь
...
Рейтинг: 0 / 0
Комбинации
    #32586236
Фотография La_Sania
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот есть функция, правда на яве, которая первоначально берет отсортированный массив с буквами или цифрами.

Каждый раз когда вызывается эта функция, она выдает следующую комбинацию элементов в массиве (меняя что-то в нем местами).
Никакой рекурсии.

И возвращает правду если есть еще комбинации, или неправду если комбинации кончились. Когда комбинации кончаются, то функция сортирует массив, приводя его в первоначальный порядок.

Это то что ты хотел?


Код: 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.
// --------------------
// NextPermutation.java
// --------------------
public class Arrays {
    public static void swap (char[] a, int i, int j) {
        if (i != j) {
            a[i] ^= a[j];
            a[j] ^= a[i];
            a[i] ^= a[j];}}

    public static void reverse (char[] a, int b, int e) {
        --e;
        while (b < e)
            swap(a, b++, e--);}

    public static boolean nextPermutation (char[] a) {
        if (a.length <  2 )
            return false;

        int i = a.length -  1 ;
        int j = a.length;
        while (true) {
            if (a[--i] < a[--j]) {
                int k = a.length;
                while (!(a[i] < a[--k]))
                    {}
                swap(a, i, k);
                reverse(a, j, a.length);
                return true;}

            if (i ==  0 ) {
                reverse(a,  0 , a.length);
                return false;}}}}


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


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