Число отдельных последовательностей фиксированной длины, которые могут быть сгенерированы с использованием заданного набора чисел

Question

Я пытаюсь найти различные последовательности фиксированной длины, которые могут быть сгенерированы с использованием чисел из заданного набора (отдельные элементы), так что каждый элемент из набор должен появиться в последовательности. Ниже приведена моя логика:

например. Пусть множество состоит из S элементов, и мы должны генерировать последовательности длины K (K> = S)

1) Сначала нам нужно выбрать S мест из K и поместить каждый элемент из набора в случайном порядке. Итак, C (K, S) * S!

2) После этого оставшиеся места могут быть заполнены из любых значений из набора. Таким образом, коэффициент

(K-S)^S следует умножить.

Таким образом, общий результат

C (K, S) S! ((K-S)^S)

Но, я получаю неправильный ответ. Пожалуйста помоги.

PS: C (K, S): количество способов выбора элементов S из элементов K (K> = S) независимо от порядка. Кроме того, ^: символ мощности т.е. 2^3 = 8.

Вот мой код в Python:

# m is the no. of element to select from a set of n elements 
# fact is a list containing factorial values i.e. fact[0] = 1, fact[3] = 6& so on. 
def ways(m,n): 
    res = fact[n]/fact[n-m+1]*((n-m)**m) 
    return res 

Answer 1

Что вы ищете число сюръективных функций домена которых представляет собой набор из K элементов (K-позиции, которые мы заполняем в выходной последовательности), а изображение представляет собой набор элементов S (ваш набор входных данных). Я думаю, что это должно работать:

static int Count(int K, int S) 
    { 
     int sum = 0; 
     for (int i = 1; i <= S; i++) 
     { 
      sum += Pow(-1, (S-i)) * Fact(S)/(Fact(i) * Fact(S - i)) * Pow(i, K); 
     } 
     return sum; 
    } 

... где Pow и Fact то, что можно было бы ожидать.

Отъезд this math.se question.

Вот почему ваш подход не сработает. Я не проверял код, просто ваше объяснение логики позади него, но я уверен, что понимаю, что вы пытаетесь сделать. Возьмем, например, K = 4, S = {7,8,9}. Рассмотрим последовательность 7,8,9,7. Это уникальная последовательность, но вы можете получить к нему:

• Произвольно выбирающих позиции 1,2,3, заполняя их в случайном порядке с 7,8,9 (ваш шаг 1), затем случайным образом выбирают 7 для оставшаяся позиция 4 (ваш шаг 2).

• Случайно выбирая позиции 2,3,4, заполняя их случайным образом 8,9,7 (ваш шаг 1), а затем произвольно выбирая 7 для оставшейся позиции 1 (ваш шаг 2).

По вашей логике вы будете считать это в обоих направлениях, хотя его следует учитывать только один раз, так как конечный результат тот же. И так далее ...