Задачка из комбинаторики

[Георгий2]

Помогите пожалуйста реализовать такое:
Имеется N ячеек и M фишек (N>M), в ячейке может находится не более K фишек, требуется сгенерировать все возможные варианты распределения фишек по этим ячейкам, причём ячейки могут быть и пустыми тоже. То есть может быть и вариант когда все фишки лежат в одной ячейке, а остальные пустые (конечно, если это не противоречит условию по K)

Пытался читать книжки по комбинаторике, но склад ума совершенно нематематический - не смог даже понять, к какому типу отнести мою задачку - перестановки ли, сочетания ли?
Готовые алгоритмы на VB не смог найти.

Спасибо всем откликнувшимся

[tyomitch]

Тести.

Код: Выделить всё

Option Explicit
DefInt A-Z

Sub Main()
Const N = 4, M = 3, K = 2
Generate "", N, M, K
End Sub

Sub Generate(ByVal Prefix$, ByVal N, ByVal M, ByVal K)
    If N = 1 Then
        If M <= K Then
            Debug.Print Prefix & M
        End If
    Else
        Dim i
        For i = 0 To K
            If i <= M Then
                Generate Prefix & i & ",", N - 1, M - i, K
            End If
        Next
    End If
End Sub


[Георгий2]

tyomitch !
Огромное спасибо! Вроде всё работает как надо!

[Георгий2]

tyomitch, здравствуйте !

всё же что-то не так, я проверил при N = 4, M = 3, K = 3, прога выдаёт такую последовательность:
0,0,2,1
0,0,3,0
0,1,0,2
0,1,1,1
0,1,2,0
0,2,0,1
0,2,1,0
0,3,0,0
1,0,0,2
1,0,1,1
1,0,2,0
1,1,0,1
1,1,1,0
1,2,0,0
2,0,0,1
2,0,1,0
2,1,0,0
3,0,0,0

при "мозго-ручном" методе получаются ещё 2 комбинации:
0,0,1,2
0,0,0,3

PS
Несмотря на лаконичность кода, не смог понять куда вставить счётчик, чтоб получать общее количество комбинаций, куда не попытался вставить - не получается 20 комбинаций

[tyomitch]

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

[Георгий2]

Господи, как я лажанулся! ИЗВИНИТЕ!

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

[tyomitch]

Там, где Debug.Print, допиши c=c+1. Объяви c на уровне модуля.

[Георгий2]

Клянусь, это было первое что я сделал, но при этом изменил и К , но по рассеяности сравнил с посчитанным при предыдущем К, естественно не совпало, а я сделал "выводы", дубина!

tyomitch, Просто ОГРОМНОЕ вам спасибо!!! особливо за ваше всегдашнее терпение к моим глупым вопросам!