Алгоритм и программа расчета числа сочетаний для больших чисел без вычисления промежуточных факториалов путем их разложения на простые множители и сокращений

В Internet встречается задача: «Найти все комбинации m по n, при этом m и n могут быть очень большими числами, вплоть до нескольких десятков тысяч» и предлагаются различные методы ее решения, в том числе и верные, т. е. работающие [1]. Существуют также on-line калькуляторы факториалов [2] и числа сочетаний [3]. Проблема возникает потому, что при использовании классической комбинаторной формулы числа сочетаний:

.

где: n — число элементов в исходном множестве; m — число элементов в подсистеме, для расчета числа сочетаний необходимо предварительно рассчитать значения факториалов, а они в большинстве языков программирования могут быть рассчитаны для значений аргумента, не превосходящим 170, а иногда и еще меньше, например 30.

Для решения этой проблемы предлагается следующий алгоритм, отличающийся от имеющихся в Internet:

• 1. Найти все простые числа меньшие заданного параметра n.
• 2. Сформировать массив чисел числителя.
• 3. Сформировать массив простых сомножителей чисел числителя.
• 4. Сформировать массив чисел знаменателя.
• 5. Сформировать массив простых сомножителей чисел знаменателя.
• 6. Сформировать массив простых сомножителей числителя, не входящих в массив простых сомножителей знаменателя.
• 7. Перемножить массив уникальных простых сомножителей числителя.

На рисунках 1 и 2 приводятся экранные формы для задания параметров расчета числа сочетаний для расчета одного значения и массива значений:

Рисунок 1. Экранная форма для задания расчета одного значения числа сочетаний Рисунок 2. Экранная форма для задания расчета массива значений числа сочетаний На рисунке 3 и в таблице 1 приведены результаты расчетов:

Рисунок 3. Результат расчета значения числа сочетаний Отметим, что далеко не каждый on-line калькулятор позволяет посчитать число сочетаний из 10 000 по 5, который без проблем рассчитывается по предложенному алгоритму прилагаемой программой. Это говорит о том, что предлагаемый алгоритм может быть востребован. Но вот, например, сайт Вольфрам-математики [3], дает тот же результат: 832 500 291 625 001 984.

Таблица 1 — Пример расчета числа сочетаний при различных значениях n и m.

Ниже приводится исходный текст программы на языке программирования xBase++: массив знаменатель числитель программирование.

© Расчет числа сочетаний для больших чисел без промежуточного расчета факториалов путем разложения их на простые множители и сокращения, beta-version, rel: 12.06.2013.

© д.э.н., к.т.н., профессор Луценко Евгений Вениаминович, Россия, Краснодар.

PROCEDURE AppSys.

// Рабочий стол остается окном приложения.

RETURN.

FUNCTION Main ().

LOCAL GetList[0], GetOptions, nColor, oMessageBox, oMenuWords, oDlg, ;

oMenuBar, oMenu1, oMenu2,oMenu3,oMenu4,oMenu5,oMenu6,oMenu7,; oMenu3₃.

DC_IconDefault (1000).

SET DECIMALS TO 15.

SET DATE GERMAN.

SET ESCAPE On.

SET COLLATION TO SYSTEM // Руссификация.

*SET COLLATION TO ASCII // Руссификация.

PUBLIC aSay[30], Mess97, Mess98, Mess99 // Массив сообщений отображаемых стадий исполнения (до 30 на экране).

PUBLIC Time_progress, Wsego, oProgress, lOk.

PUBLIC nEvery := 100 // Количество корректировок прогресс-бар

g = 0.

s = 0.

mRegim = 1.

@g, 0 DCGROUP oGroup1 CAPTION 'Задайте вариант использования программы:' SIZE 62.0, 7.0.

@++s, 2 DCRADIO mRegim VALUE 1 PROMPT 'Расчет одного конкретного значения числа сочетаний из N по M' PARENT oGroup1.

@++s, 2 DCRADIO mRegim VALUE 2 PROMPT 'Расчет таблицы значений числа сочетаний для диапазонов N и M' PARENT oGroup1.

s = 3.

mN1 = 30.

mM1 = 2.

@++s+0.2,12 DCSAY «Задайте значение N:» EDITPROTECT {||.NOT.mRegim=1} HIDE {||.NOT.mRegim=1} PARENT oGroup1.

s , 27 DCSAY «» GET mN1 PICTURE «#######» EDITPROTECT {||.NOT.mRegim=1} HIDE {||.NOT.mRegim=1} PARENT oGroup1

@++s+0.2,12 DCSAY «Задайте значение M:» EDITPROTECT {||.NOT.mRegim=1} HIDE {||.NOT.mRegim=1} PARENT oGroup1.

s , 27 DCSAY «» GET mM1 PICTURE «#######» EDITPROTECT {||.NOT.mRegim=1} HIDE {||.NOT.mRegim=1} PARENT oGroup1

s = 3.

N1 = 1.

N2 = 30.

M1 = 1.

M2 = N2.

@++s+0.2, 5 DCSAY «Задайте диапазон значений N:» EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1.

s , 27 DCSAY «» GET N1 PICTURE «#######» EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1

s , 37 DCSAY «» GET N2 PICTURE «#######» EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1

@++s+0.2, 5 DCSAY «Задайте диапазон значений M:» EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1.

s , 27 DCSAY «» GET M1 PICTURE «#######» EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1

s , 37 DCSAY «» GET M2 PICTURE «#######» EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1

DCGETOPTIONS TABSTOP.

DCREAD GUI ;

FIT ;

OPTIONS GetOptions ;

ADDBUTTONS;

MODAL ;

TITLE '© Луценко Е. В. Расчет сочетаний для больших чисел'.

IF mRegim = 1.

oScr := DC_WaitOn ().

Mess := {}.

IF mN1 <= 21.

AADD (Mess, «Число сочетаний из N=# по M=$ по классической формуле с факториалами: С (n, m) = n! / (m! (n-m)!) = «+ALLTRIM (STR (INT (Cf (mN1,mM1))))).

ELSE.

AADD (Mess, «Число сочетаний из N=# по M=$ по формуле с факториалами: С (n, m)=n!/(m!(n-m)!) не может быть рассчитано !»).

ENDIF.

AADD (Mess, «Число сочетаний из N=# по M=$ по алгоритму с сокр. простых множителей: С (n, m) = P (m+1,n)/P (1,n-m) = «+C (mN1,mM1)).

AADD (Mess, «где: P (a, b)=a*(a+1)*(a+2)*…*b: произведение целых чисел от a до b с шагом 1»).

DC_Impl (oScr).

Mess[1] = STRTRAN (Mess[1], «#», ALLTRIM (STR (mN1,15))).

Mess[1] = STRTRAN (Mess[1], «$», ALLTRIM (STR (mM1,15))).

Mess[2] = STRTRAN (Mess[2], «#», ALLTRIM (STR (mN1,15))).

Mess[2] = STRTRAN (Mess[2], «$», ALLTRIM (STR (mM1,15))).

LB_Warning (Mess, «© Луценко Е. В. Расчет числа сочетаний для больших чисел»).

ENDIF.

IF mRegim = 2.

aStructure := { { «N», «C», 15, 0} }

FOR j=N1 TO N2.

FieldName = «M» +ALLTRIM (STR (j, 21)).

AADD (aStructure, { FieldName, «C», 250, 0 }).

NEXT.

DbCreate («Cnm.dbf», aStructure).

nMax = 0;FOR mn=N1 TO N2;FOR mm=1 TO mn;++nMax;NEXT;NEXT.

Mess = 'Расчет числа сочетаний из n по m'.

@ 4,5 DCPROGRESS oProgress SIZE 70,1.1 MAXCOUNT nMax COLOR GRA_CLR_CYAN PERCENT EVERY 100.

DCREAD GUI TITLE Mess PARENT @oDialog FIT EXIT.

oDialog:show ().

nTime = 0.

CLOSE ALL.

USE Cnm EXCLUSIVE NEW.

SELECT Cnm.

DC_GetProgress (oProgress, 0, nMax).

FOR mn = N1 TO N2.

APPEND BLANK.

FIELDPUT (1, «N» +ALLTRIM (STR (mn, 21))).

FOR mm = 1 TO mn.

FIELDPUT (1+mm, C (mn, mm)).

DC_GetProgress (oProgress, ++nTime, nMax).

NEXT.

NEXT.

DC_GetProgress (oProgress, nMax, nMax).

oDialog:Destroy ().

Mess := {}.

AADD (Mess, 'Результаты расчета числа сочетаний C (n, m) в базе данных Cnm. dbf').

AADD (Mess, 'Из-за большой размерности числа в БД Cnm. dbf представлены в текстовом формате').

AADD (Mess, 'Заданием в MS Excel формата ячеек «числовой» они преобразутся в числовой формат').

LB_Warning (Mess, «© Луценко Е. В. Расчет числа сочетаний для больших чисел»).

ENDIF.

CLOSE ALL.

RETURN NIL.

С (n, m) = n! / (m! (n — m)!) число сочетаний из n по m.

FUNCTION Cf (n, m).

RETURN (Fact (n)/(Fact (m)*Fact (n-m))).

С (n, m) = n! / (m! (n — m)!) число сочетаний из n по m для больших чисел без вычисления промежуточных факториалов путем разложения.

факториалов на простые множители и их сокращений С (n, m) = P (m+1,n) / P (1,n-m), где P (a, b) произведение целых чисел от a до b с шагом 1.

• 1. Найти все простые числа меньшие n
• 2. Сформировать массив чисел числителя
• 3. Сформировать массив простых сомножителей числителя
• 4. Сформировать массив чисел знаменателя
• 5. Сформировать массив простых сомножителей чисел знаменателя
• 6. Сформировать массив простых сомножителей числителя, не входящих в массив простых сомножителей знаменателя
• 7. Перемножить массив уникальных простых сомножителей числителя

FUNCTION C (n, m).

1. Найти все простые числа меньшие n, включая 1 и допуская n=1 aPrCh := {} // Массив простых чисел.

IF n = 1.

AADD (aPrCh, 1).

ELSE.

FOR j = 2 TO n.

Проверка, является ли j простым числом.

Flag = .T.

FOR i=2 TO j-1.

IF j=i*INT (j/i) // Делится ли j на i нацело?

Flag = .F.

EXIT.

ENDIF.

NEXT.

IF Flag.

AADD (aPrCh, j).

ENDIF.

NEXT.

ENDIF.

• * DC_DebugQout (aPrCh)
• 2. Сформировать массив чисел числителя

aChis := {}.

IF m = n.

AADD (aChis, 1).

ELSE.

IF m < n.

FOR j=m+1 TO n.

AADD (aChis, j).

NEXT.

ENDIF.

ENDIF.

DC_DebugQout (aChis).

3. Сформировать массив простых сомножителей числителя.

aPSChis := {}

FOR i=1 TO LEN (aChis)

***** Разложить число на простые множители

aPrMn := {} // Массив простых множителей числа: Chislo.

Chislo = aChis[i].

IF Chislo = 1.

AADD (aPrMn, 1).

ELSE.

Flag = .T.

DO WHILE Flag.

FOR j=1 TO LEN (aPrCh).

**** Проверка, делится ли Chislo на простое число из массива aPrCh.

Flag = .F.

IF Chislo = aPrCh[j] * INT (Chislo/aPrCh[j]).

AADD (aPrMn, aPrCh[j]).

Chislo = Chislo/aPrCh[j].

Flag = .T.

EXIT.

ENDIF.

NEXT.

ENDDO.

ENDIF.

***** Занести простые множители числа aChis[j] в массив простых сомножителей числителя.

FOR j=1 TO LEN (aPrMn).

AADD (aPSChis, aPrMn[j]).

NEXT.

NEXT.

• * DC_DebugQout (aPSChis)
• ***** 4. Сформировать массив чисел знаменателя

aZnam := {}.

IF m = n.

AADD (aZnam, 1).

ELSE.

IF m < n.

FOR j=1 TO n — m.

AADD (aZnam, j).

NEXT.

ENDIF.

ENDIF.

• * DC_DebugQout (aZnam)
• ******* 5. Сформировать массив простых сомножителей чисел знаменателя

aPSZnam := {}.

FOR i=1 TO LEN (aZnam).

***** Разложить число на простые множители.

aPrMn := {} // Массив простых множителей числа: Chislo.

Chislo = aZnam[i].

IF Chislo = 1.

AADD (aPrMn, 1).

ELSE.

Flag = .T.

DO WHILE Flag.

FOR j=1 TO LEN (aPrCh).

**** Проверка, делится ли Chislo на простое число из массива aPrCh.

Flag = .F.

IF Chislo = aPrCh[j] * INT (Chislo/aPrCh[j]).

AADD (aPrMn, aPrCh[j]).

Chislo = Chislo/aPrCh[j].

Flag = .T.

EXIT.

ENDIF.

NEXT.

ENDDO.

ENDIF.

*** Занести простые множители числа aZnam[j] в массив простых сомножителей знаменателя.

FOR j=1 TO LEN (aPrMn).

AADD (aPSZnam, aPrMn[j]).

NEXT.

NEXT.

• * DC_DebugQout (aPSZnam)
• ******** 6. Сформировать массив простых сомножителей числителя,
• ******** не входящих в массив простых сомножителей знаменателя

aPS:= {}.

FOR j=1 TO LEN (aPSChis).

Pos = ASCAN (aPSZnam, aPSChis[j]).

IF Pos = 0.

AADD (aPS, aPSChis[j]).

ELSE.

aPSZnam[Pos] = 1 // Сокращение простых сомножителей числителя и знаменателя.

ENDIF.

NEXT.

• * DC_DebugQout (aPS)
• ******** 7. Перемножить массив уникальных простых сомножителей числителя и знаменателя

mMulChis = 1.

FOR j=1 TO LEN (aPS).

mMulChis = mMulChis * aPS[j].

NEXT.

mMulZnam = 1.

FOR j=1 TO LEN (aPSZnam).

mMulZnam = mMulZnam * aPSZnam[j].

NEXT.

DC_DebugQout (mMulChis, mMulZnam, mMulChis/mMulZnam).

RETURN (ALLTRIM (STR (mMulChis/mMulZnam, 250))).

FUNCTION LB_Warning (message, ctitle).

LOCAL aMsg := {}.

DEFAULT cTitle TO ''.

IF valtype (message) # 'A'.

aadd (aMsg, message).

ELSE.

aMsg := message.

ENDIF.

IF LEN (ALLTRIM (cTitle)) > 0.

DC_MsgBox (, aMsg, cTitle).

ELSE.

DC_MsgBox (, aMsg,'Универсальная когнитивная аналитическая система «Эйдос-Х++» ').

ENDIF.

Выводы Материалы данной статьи могут быть использованы в учебном процессе при преподавании дисциплин: «Алгоритмы и структуры данных», «Дискретная математика», «Численные методы», «Основы статистики и комбинаторики» и других.