Как посчитать общее количество возможных комбинаций строки с использованием c #?

Question

Я хочу решить алгоритм, в котором у меня есть этот ввод:

n = 30 и st = 1234321

Теперь я хочу посмотреть, сколько комбинаций можно сформировать, используя строку, т.е. может иметь

(1 2 3 4 2 1)
(1 23 4 3 2 1)
(1 2 3 4 3 21 )
( 12 3 4 3 2 1)
( 12 3 4 3 21 )
(1 23 4 3 21 )

т.е. всего меньше 30. Так что всего комбинаций будет 6.

Но мы подсчитываем строку в подсчетах, когда у нас либо один из 0 присутствует, либо как ведущий, например 09.

возьмем случай: n = 70 и st = 8675309. Теперь в этом случае имеем:

(8 6 7 5 3 0 9)
(8 67 5 3 0 9)
(8 6 7 53 0 9)
(8 6 7 5 30 9)
(8 6 7 5 3 09 )
(8 67 53 0 9)
(8 67 5 30 9)
(8 67 5 3 09 )

здесь общее количество равно 2 только как (мы не считаем, если у нас есть либо 0 присутствующих в одиночку, либо ведущие, например 09).

Пожалуйста, предложите мне c # код для поиска таких комбинаций.

Answer 1

Вы можете смоделировать свое пространство как двоичное дерево: на n-ом уровне левый дочерний элемент соединяет n -й и n+1-й числа в списке, а правый дочерний - нет.Используйте DFS и сокращайте ветви, которые запрещены вашими ограничениями, а затем подсчитывайте конечные узлы.

Answer 2

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

1) Get all unique sub string values
2) Get all permutations for these values
3) then remove any that add up to be over 60
4) do step 2 again

Обсуждаются шаги со 2 по 4 здесь

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

Answer 3

Вот ссылка на учебник и код для класса перестановки строк в C #. Я не собираюсь переводить ваши цифры в этот код для вас, потому что он очень прост.

Удачи!