Algoritmo di numeri di campana

Question

Sto provando a scrivere un algoritmo per scoprire il numero di modi in cui è possibile ordinare n numeri. Ad esempio, due numeri dicono che a e b possono essere ordinati in 3 modi ..

Analogamente, 3 numeri possono essere disposti in 13 modi.

Ho scoperto che posso risolvere il problema utilizzando la programmazione dinamica. Ed ecco quello che sto pensando di avere strati che rappresentano diversi ordinamenti. Ex. a > b hanno due livelli e a = b ha un singolo livello e così via. In modo che io possa usarlo per scopi successivi come fatto nella programmazione dinamica. Ma non sono in grado di scrivere una relazione di ricorrenza per lo stesso. Qualcuno può suggerirmi come posso scriverlo?

Answer 1

Supponiamo f (n, k) = numero di modi possibili per avere k disuguaglianza (e così nk-1 uguaglianza), quindi: suppone che si abbia n-1 il numero, ora si vuole per aggiungere un altro numero e calcolare f (n, k), allora abbiamo due possibilità lità:

1) Ci sono (in-k) disuguaglianze in quei numeri (n-1) e ci sono (k + 1) (f (n-1, k-1)) modi per aggiungere n ' il numero in modo da aggiungere nuove disuguaglianze.

2) Ci sono k diseguaglianze in quei numeri (n-1), e ci sono (k + 1) (f (n-1, k)) modi per aggiungere n ° numero senza disuguaglianza aggiuntiva.

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

e ciò che si vuole è la somma di loro (da zero a n-1), il codice Bellow è in C# (appena testato per i casi semplici), infatti Abbiamo appena calcoliamo il numero di modi possibili non generano tutti i modi ..

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

Onestamente, penso che risolverlo tramite programmazione dinamica è come uccidere la formica con una mitragliatrice.

È assolutamente necessario utilizzare la combinatoria, perché non dovrebbe essere così difficile.

Quando non c'è l'uguaglianza, la sua n! (permutazione), allora devi contare combinazioni (tutti uguali n-tuple), quindi la sua per 3

3! + 2 * (3 sopra 2) + (3 su 3) = 13

Answer 3

I seguenti C# uscite del programma sia il numero di ordinamenti, e gli ordinamenti stessi:

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

uscita Esempio (per 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

Ho trovato che il On-Line Encyclopedia of Integer Sequences è una grande risorsa per problemi come questo. Hai dato abbastanza informazioni per ottenere anche la risposta. Chiaramente per il caso degenere di numeri zero, è possibile solo un ordine. Inoltre esiste un solo ordine per un singolo numero. Per due, hai detto che ci sono tre ordini e per tre interi ce ne sono tredici. Cerca 1,1,3,13 e la prima partita che appare è this one, "Numero di modi in cui i concorrenti possono classificarsi in una competizione, consentendo la possibilità di legami". Da lì vedrai i primi venti circa in questa sequenza e il contenuto che le persone hanno contribuito alla sequenza.Elencati tra gli altri, è una soluzione ricorsiva in Mathematica (riformattato e ampliato qui per chiarimenti):

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

che si potrebbe implementare facilmente in un'altra lingua, se si preferisce.

Spero che questo aiuti e che trovi l'OEIS utile in futuro!