Pertanyaan Algoritma Bilangan Bell


Saya mencoba menulis algoritme untuk mencari tahu jumlah cara nomor n dapat dipesan. Misalnya, dua nomor mengatakan a dan b dapat dipesan dalam 3 cara ..

Demikian pula, 3 angka dapat diatur dalam 13 cara.

Saya menemukan bahwa saya dapat memecahkan masalah menggunakan pemrograman dinamis. Dan inilah yang saya pikirkan untuk memiliki lapisan yang mewakili urutan yang berbeda. Ex. a > b memiliki dua lapisan dan a = b memiliki satu lapisan dan seterusnya. Sehingga saya bisa menggunakannya untuk keperluan selanjutnya seperti yang dilakukan dalam pemrograman dinamis. Tapi saya tidak bisa menulis relasi pengulangan untuk hal yang sama. Dapatkah seseorang menyarankan saya bagaimana saya bisa menulis itu?


5
2017-11-07 08:36


asal


Jawaban:


Asumsikan f (n, k) = jumlah cara yang mungkin dengan memiliki k ketidaksetaraan (dan persamaan n-k-1), jadi: asumsikan Anda memiliki nomor n-1, sekarang Anda ingin menambahkan nomor lain dan menghitung f (n, k), maka kita memiliki dua kemungkinan:

1) Ada ketidaksesuaian (k-1) pada angka-angka (n-1), dan ada (k + 1) (f (n-1, k-1)) cara untuk menambahkan nomor n'th sehingga ketidaksetaraan baru ditambahkan.

2) Ada ketidaksetaraan k dalam angka-angka (n-1), dan ada (k + 1) (f (n-1, k)) cara untuk menambahkan nomor n'th tanpa tambahan ketidaksetaraan.

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

dan apa yang Anda inginkan adalah jumlah dari mereka (dari nol ke n-1), kode bawah dalam c # (hanya diuji untuk kasus-kasus sederhana), pada kenyataannya Kami hanya menghitung sejumlah cara yang mungkin tidak menghasilkan semua cara ..

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

1
2017-11-07 11:25



Saya telah menemukan bahwa On-Line Encyclopedia of Integer Sequences adalah sumber daya yang bagus untuk masalah seperti ini. Anda telah memberikan informasi yang cukup untuk mendapatkan jawabannya juga. Jelas untuk kasus degenerasi angka nol, hanya satu pemesanan yang mungkin. Juga hanya ada satu pesanan untuk satu nomor. Untuk dua, Anda mengatakan ada tiga urutan dan untuk tiga bilangan bulat ada tiga belas. Cari 1,1,3,13 dan pertandingan pertama yang muncul yang ini, "Jumlah cara n pesaing bisa mendapat peringkat dalam suatu kompetisi, memungkinkan untuk kemungkinan adanya ikatan." Dari sana Anda akan melihat dua puluh atau lebih hasil pertama dalam urutan ini, dan sebanyak konten sebagai orang telah berkontribusi pada urutan. Tercantum di antara yang lain adalah solusi rekursif dalam Mathematica (diformat ulang dan diperluas di sini untuk klarifikasi):

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

yang bisa Anda terapkan dengan mudah dalam bahasa lain jika Anda mau.

Semoga ini membantu dan Anda menemukan OEIS bermanfaat di masa depan!


1
2017-11-07 21:53



Program C # berikut menghasilkan baik jumlah urutan, dan urutannya sendiri:

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

Contoh keluaran (untuk 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

0
2017-11-07 09:48



Sejujurnya saya berpikir, bahwa memecahkannya melalui pemrograman dinamis seperti membunuh semut dengan senapan mesin.

Anda pasti harus menggunakan kombinatorik, karena seharusnya tidak begitu sulit.

Ketika tidak ada persamaan, itu n! (permutasi), maka Anda harus menghitung kombinasi (semua sama n-tupel), jadi untuk 3

3! + 2 * (3 lebih dari 2) + (3 lebih dari 3) = 13


0
2017-11-07 08:52