Вычислить все возможные числа из заданных цифр

Проблема простая. Из заданного набора цифр (максимум 10 цифр) вычислите все числа, которые могут быть образованы из этих цифр (цифру можно использовать столько раз, сколько она входит в набор).

Во-первых, я думаю об использовании грубой силы и перебора всех возможных комбинаций, но количество комбинаций равно факториалу N, где N - количество цифр. И даже если это возможно, как я могу запустить все возможные комбинации без использования 10 циклов for?

Во-вторых, я попытался поместить все эти цифры в строку и стереть одну из строки, положить конец и продолжать пытаться вот так, но это, вероятно, не даст никаких возможных комбинаций, и даже если это так, я не верю буду в разумные сроки.

Я уверен, что должен быть более быстрый и лучший алгоритм для получения всех возможных чисел из заданного набора цифр.

Я нашел один код в Интернете, и он:

#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;
}

c++ algorithm digits permutation
person Stefan4024    schedule 31.03.2013    source источник
comment
Можно ли поставить одну и ту же цифру на разные позиции? Например, учитывая {1,2}, можете ли вы сделать 11, 12,22,21? Я имею в виду, можно ли выбрать одну и ту же цифру более одного раза?   -  person taocp    schedule 01.04.2013
comment
@SongWang Думаю, в вашем случае это было дважды {1,1,2,2}.   -  person mlt    schedule 01.04.2013
comment
возможный дубликат алгоритма C ++ для N! заказы   -  person John Kugelman    schedule 01.04.2013
comment
@ Stefan4024 Вам нужно несколько комбинаций? Или собственно комбинации?   -  person mlt    schedule 01.04.2013
comment
Нет, для {1,2} вы должны распечатать или вставить вектор только 12 и 21. Я думаю, что я указал это в вопросе   -  person Stefan4024    schedule 01.04.2013

Ответы (1)


arrow_upward
0
arrow_downward

Мой подход может показаться немного запутанным, но сначала я дам обзор и очень простой фрагмент кода (не на том языке).

Как вы говорите, вам принципиально нужны все перестановки ваших элементов. Таким образом, очевидным подходом было бы использование библиотечной функции, которая уже делает это. Возможно, std :: 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,

... конечно, вам, возможно, придется поработать немного по-другому, если вы хотите распечатать эти перестановки в каком-то определенном порядке, а не в каком-либо методе .keys () и itertools.permutations () выполняет. (Это детали реализации).

Итак, можете ли вы создать такое сопоставление, перебрать перестановку его ключей и выполнить разыменование карты при возврате / печати результатов?

person Jim Dennis    schedule 31.03.2013
comment
Теги указывают на то, что здесь мы имеем дело с вопросом, относящимся к C ++. Использование библиотеки Python, вероятно, не вариант. - person jwueller; 01.04.2013
comment
Ой. Не заметил, что это вопрос C ++. - person Jim Dennis; 01.04.2013