Thuật toán số Chuông

Question

Tôi đang cố gắng viết một thuật toán để tìm ra số cách có thể đặt số n. Ví dụ, hai số nói a và b có thể được đặt theo 3 cách ..

Tương tự, 3 số có thể được sắp xếp theo 13 cách.

Tôi phát hiện ra rằng tôi có thể giải quyết vấn đề bằng cách sử dụng lập trình động. Và đây là những gì tôi đang nghĩ để có các lớp đại diện cho thứ tự khác nhau. Ví dụ a > b có hai lớp và a = b có một lớp và vân vân. Vì vậy, tôi có thể sử dụng nó cho các mục đích sau này như được thực hiện trong lập trình động. Nhưng tôi không thể viết một mối quan hệ lặp lại cho cùng một. Ai đó có thể đề nghị tôi làm thế nào tôi có thể viết điều đó?

Answer 1

giả sử f (n, k) = số cách có thể bằng cách k bất bình đẳng (và do đó nk-1 bình đẳng), do đó: giả sử bạn có n-1 số, bây giờ bạn muốn để thêm một số khác và tính f (n, k), sau đó chúng ta có hai possibi lity:

1) Có (k-1) bất bình đẳng trong số (n-1) số, và có (k + 1) (f (n-1, k-1)) cách thêm n ' th số để bất bình đẳng mới được thêm vào.

2) Có k bất bình đẳng trong số (n-1) số, và có (k + 1) (f (n-1, k)) cách thêm số thứ n mà không có bất bình đẳng bổ sung.

f(n,k) = (k+1)(f(n-1,k-1) + f(n-1,k)) 

và những gì bạn muốn là tổng của chúng (từ zero đến n-1), mã Bellow là trong C# (chỉ kiểm tra đối với trường hợp đơn giản), trên thực tế chúng tôi chỉ tính số cách có thể không tạo ra tất cả các cách ..

class EqualInequalPermutation 
{ 
    public int OrderingsNumber(int n) 
    { 
     int[][] f = new int[n+1][]; 
     for (int i = 0; i < n+1; i++) 
     { 
      f[i] = new int[n]; 
      for (int j = 0; j < n; j++) 
       f[i][j] = 0; 
     } 
     f[1][0] = 1; 
     int factorial = 1; 
     for (int i = 1; i <= n; i++) 
     { 
      f[i][0] = 1; 
      factorial *= i; 
      f[i][i - 1] = factorial; 
      for (int k = 1; k < n; k++) 
      { 
       f[i][k] = (k + 1) * (f[i - 1][k - 1] + f[i - 1][k]); 
      } 
     } 
     int answer = 0; 
     for (int i = 0; i < n; i++) 
     { 
      answer += f[n][i]; 
     } 
     return answer; 
    } 
} 

Answer 2

Tôi thành thật nghĩ rằng, giải quyết nó thông qua lập trình động cũng giống như giết chết con kiến ​​bằng súng máy.

Bạn chắc chắn nên sử dụng tổ hợp, vì nó không quá khó.

Khi không có sự bình đẳng, nó n! (hoán vị), sau đó bạn phải đếm kết hợp (tất cả bằng n-tuples), do đó nó cho 3

3! + 2 * (3 so với 2) + (3 trên 3) = 13

Answer 3

Sau đây chương trình C# đầu ra cả số lượng orderings, và orderings mình:

static void Main(string[] args) 
{ 
    if (args.Length < 1) 
    { 
     Console.WriteLine("Missing argument - the number of items"); 
     return; 
    } 
    int n; 
    if (!int.TryParse(args[0], out n)) 
    { 
     Console.WriteLine("Could not parse number of items"); 
     return; 
    } 
    if (n < 0) 
    { 
     Console.WriteLine("Number of items must not be negative"); 
     return; 
    } 
    var count = GetOrderings(n); 
    Console.WriteLine("Total: {0}", count); 
} 

private static int GetOrderings(int n) 
{ 
    var items = Enumerable.Range(0, n).Select(i => (char)('a' + i)).ToList(); 
    // Produce distinct orderings of the input items 
    return GetOrderings(new List<char>(), items); 
} 

private static int GetOrderings(List<char> current, List<char> items) 
{ 
    // If we have a complete permutation in current, produce the possible arrangements of signs between them 
    if (items.Count == 0) return GetSigns(new List<char>(), current, 0); 
    var result = 0; 
    for (var i = 0; i < items.Count; i++) 
    { 
     // nextCurrent = current + i'th element of items 
     var nextCurrent = new List<char>(current) { items[i] }; 
     // nextItems = items excluding the i'th element 
     var nextItems = new List<char>(items.Where((c, n) => n != i)); 
     result += GetOrderings(nextCurrent, nextItems); 
    } 
    return result; 
} 

private static int GetSigns(List<char> signs, List<char> items, int n) 
{ 
    if (signs.Count >= items.Count - 1) 
    { 
     // Once we have sufficient signs, write out the items interleaved with them 
     var str = string.Empty; 
     for (var i = 0; i < items.Count; i++) 
     { 
      if (i > 0) str += signs[i - 1]; 
      str += items[i]; 
     } 
     Console.WriteLine(str); 
     return 1; 
    } 
    var result = GetSigns(new List<char>(signs) { '<' }, items, n + 1); 
    // To prevent duplicate orderings, only allow "=" between two items if they are in lexicographic order 
    // (i.e. allow "a = b" but not "b = a") 
    if (items[n] >= items[n + 1]) return result; 
    return result + GetSigns(new List<char>(signs) { '=' }, items, n + 1); 
} 

Ví dụ đầu ra (cho n = 3):

a<b<c 
a<b=c 
a=b<c 
a=b=c 
a<c<b 
a=c<b 
b<a<c 
b<a=c 
b<c<a 
b=c<a 
c<a<b 
c<a=b 
c<b<a 
Total: 13

Answer 4

Tôi đã tìm thấy rằng On-Line Encyclopedia of Integer Sequences là tài nguyên tuyệt vời cho các vấn đề như thế này. Bạn đã cung cấp đủ thông tin để nhận câu trả lời. Rõ ràng đối với trường hợp thoái hóa của các số không, chỉ có một thứ tự là có thể. Cũng chỉ có một đơn hàng tồn tại cho một số duy nhất. Đối với hai, bạn nói có ba thứ tự và cho ba số nguyên có mười ba. Tìm kiếm 1,1,3,13 và trận đấu đầu tiên bật lên là this one, "Số cách mà các đối thủ cạnh tranh có thể xếp hạng trong một cuộc thi, cho phép khả năng liên kết." Từ đó bạn sẽ thấy hai mươi kết quả đầu tiên trong chuỗi này và nhiều nội dung như mọi người đã đóng góp vào chuỗi.Liệt kê trong số những người khác là một giải pháp đệ quy trong Mathematica (định dạng lại và mở rộng vào đây để làm rõ):

f[0] = 1 
f[1] = 1 
f[n_] := f[n] = Sum[ Binomial[n,k] * f[n-k], {k,1,n}] (* memoizes the values *) 

mà bạn có thể thực hiện dễ dàng bằng ngôn ngữ khác nếu bạn thích.

Hy vọng điều này sẽ giúp bạn thấy rằng OEIS hữu ích trong tương lai!