如何获得使用给定数字可以组成的所有可能的n位数字？

Question

我正在编写一个大型应用程序的一部分，我遇到了这个问题。我将通过呈现一个类似的普通场景来让大家从所有细节中抽象出来。

我得到n（运行时要形成的数字的位数）。

我还得到了一个数字列表，如 {2,4,8,9}。

我必须从上面给定长度的列表中形成所有可能的数字。

例如如果 n = 3 且列表 = {4, 5, 6}

那么可能的数字是：

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

等等...

任何帮助将不胜感激！

问候

杀恨杀

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

我的方法如下：

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

这应该会起作用。 代码应该是不言自明的，如果不是，请发表评论。

您必须注意列表项是否可以长于一位数字。然后你需要在组合函数中添加以下内容：

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

当然还要将 n 赋予组合函数。

最后在nDigit中你必须检查是否有长度小于n的组合

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

我编写了以下 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 6

def printAll(arr, i, n):

    if i == n:#outside the array
        print(*arr)
        return 

    #at ith index
    arr[i] = 1
    printAll(arr,i+1,n)
    arr[i] = 2
    printAll(arr,i+1,n)
    return
N = 2
answer = [0]*N
printAll(answer, 0, N)

根据给定的数字更改

arr[i]

部分。