Вычислить все возможные числа из заданных цифр
Проблема проста. Из заданного набора цифр (максимум 10 цифр) вычислите все числа, которые можно сделать из этих цифр (цифра может использоваться столько раз, сколько она включена в набор).
Вначале я думаю об использовании грубой силы и прохождении всех возможных комбинаций, но количество комбинаций равно факториалу N, где N — количество цифр. И даже если это возможно, как я могу запустить все возможные комбинации, используя 10 для циклов?
Во-вторых, я попытался поместить все эти цифры в строку, а затем стереть одну из строки и положить на конец и продолжать пытаться, как это, но это, вероятно, не даст никаких возможных комбинаций, и даже если это произойдет, я не верю в это будет в разумные сроки.
Я уверен, что должен быть более быстрый и лучший алгоритм для получения всех возможных чисел из заданного набора цифр.
Я нашел один код в Интернете, и это:
#include <iostream>
#include <algorithm>
using namespace std;
int main () {
int noOfDigits;
cin >> noOfDigits;
int myints[noOfDigits];
for(int i = 0; i<noOfDigits; i++)
{
cin >> myints[i];
}
sort (myints,myints+3);
do {
for(int i = 0; i<noOfDigits;i++)
{
cout << myints[i];
}
cout << endl;
} while ( next_permutation(myints,myints+noOfDigits) );
return 0;
}
Решение
Мой подход может показаться немного запутанным, но я сначала дам обзор и очень простой пример кода (с неправильного языка).
Как вы говорите, вы в основном хотите все перестановки ваших элементов. Таким образом, очевидным подходом будет использование библиотечной функции, которая уже делает это. возможно станд :: next_permutation (Я буду использовать intertools.permutations для моего простого примера). Однако вы указываете, что у вас могут быть повторяющиеся элементы среди входного набора, что нарушает ограничение на этот инструмент.
Поэтому мой подход заключается в построении отображения между набором уникальных ключей и нашими элементами (цифрами) с их возможными дубликатами. Для небольшого числа цифр, которые вы описываете, проще всего было бы использовать отдельные символы в качестве ключей, сопоставляя их (разумеется, через словарь) с заданными элементами (цифрами). Удобный способ сделать это через string.printable. Таким образом, учитывая кортеж, список или другую последовательность «цифр» называется mydigits мы можем построить наше отображение как:
#!python
import string
digit_mapping = dict([(y,x) for x,y in zip(mydigits,string.printable)])
Оттуда все, что нам нужно сделать, это перебрать перестановки и отобразить ключи обратно к их исходным «цифрам» (в данном случае строковое представление этих «цифр»
#!python
for i in itertools.permutations(digit_mapping.keys()):
perm = ''.join([str(digit_mapping[x]) for x in i])
print perm,
… конечно, вам, возможно, придется работать немного по-другому, если вы хотите напечатать эти перестановки в каком-то определенном порядке, а не в каком бы то ни было .клавиши () метод и itertools.permutations () функция делает. (Это детали реализации).
Итак, можете ли вы создать такое отображение, перебрать перестановку его ключей и выполнить разыменование карты при возврате / печати результатов?
Другие решения
Других решений пока нет …