Как получить все возможные n-значные числа, которые могут быть сформированы с использованием заданных цифр?

Question

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

Мне дано n (число цифр числа, которое будет сформировано во время выполнения).

Мне также дают список чисел, скажем {2,4,8,9}.

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

например, если n = 3 и list = {4, 5, 6}

, тогда возможное число:

444,
445,
446,
454,
455,
456,
464,
465,
466, 

и т. Д. *

Любая помощь будет оценена!

С уважением

Shahensha

Answer 1

Вы можете использовать рекурсию.Скажите, что числа, которые вы можете использовать, находятся в массиве.

Код C #:

static int[] digits = new int[] {4, 5, 6};

static void Rec(int current, int numDigits) {
    if(numDigits==0)
        Console.WriteLine(current);
    else
        foreach(int x in digits)
            Rec(current*10+x, numDigits-1);
}

А затем позвоните:

static void Main(string[] args){
    Rec(0, 3);
}

Answer 2

Использовать рекурсивную функцию.Это пример в JavaScript ...

var result;
function recurse(n,lst,s){
  var i,c;  
  for (i=0; i<lst.length; i++){
    if(n>1)recurse(n-1,lst,s+lst[i]);
    else result.push(s+lst[i])
  }
}
function generate(n,lst){
  result=[];
  if(n>0 && lst.length>0){
    for(var i=0; i<lst.length; i++)lst[i]=''+lst[i];
    recurse(n,lst,'')
  }
  return result
}
generate(3,[4,5,6]);

Answer 3

Я написал следующий код F # для решения этой проблемы:

let rec variations rank xs = 
    match rank with
    | 1 -> 
        seq {
            for x in xs do
            yield [x]
        }

    | _ -> 
        seq {
            for x in xs do
            for y in variations (rank-1) xs do   
            yield x::y
        }

Итак,

variations 3 (seq {4..6})
|> Seq.iter (printfn "%s")

напечатает

444
445
446
454
455
...
666

все 27 значений

Answer 4

Ваша задача эквивалентна подсчету в базе, отличной от 10, как демонстрирует следующая программа на C ++:

#include <vector>
#include <iostream>

using std::vector;

unsigned int pow(unsigned int n, unsigned int m)
{
    unsigned int to_ret = 1;
    for (unsigned int i = 0; i < m; i++)
        to_ret *= n;
    return to_ret;
}

void print_all(vector<unsigned int> sym, unsigned int n)
{
    const unsigned int m = sym.size();
    unsigned int max = pow(m, n);
    char *text = new char[n + 1];
    text[n] = '\0';
    for (unsigned int i = 0; i < max; i++) {
        unsigned int to_print = i;
        for (unsigned int j = 1; j <= n; j++) {
            text[n - j] = sym[to_print % m];
            to_print /= m;
        }
        std::cout << text << std::endl;
    }
    delete[] text;
}

int main(int argc, char **argv)
{
    vector<unsigned int> a({'1','2','3','4','5'});
    print_all(a, 5);
    return 0;
}

Очевидная проблема с этим подходом заключается в простом переполнении max для высокойдостаточно значений n и m.Вы можете решить это, подражая подсчету, используя массив m связанных списков, которые должны представлять "цифры".

Answer 5

мой подход будет следующим:

list combine(list a, list b)
{
    list c;
    for ( i = 0, i < list.size(), ++i )
    {
        for ( j = 0, j < list.size(), ++j )
            c.add( a[i] * pow(10,log_10(b[j]) + 1) + b[j] );
    }
    return c;
}

, а затем для задачи с n-значным числом:

list nDigit(list a, int n)
{
    list out;
    out = combine(a, a);
    for ( i = 1, i < n, ++i )
        out = combine(a, out);
    return out;
}

это должно сделать магию. Код должен быть понятен, если нет, оставьте комментарий.

Вам придется обратить внимание, если элементы списка могут быть длиннее цифры. Затем вам нужно добавить следующее в функцию объединения:

* * 1010

и, конечно, передайте функцию объединения.

В конце концов, в nDigit вы должны проверить, есть ли комбинации с длиной, меньшей n