Algoritmo de números de campana

Question

Estoy tratando de escribir un algoritmo para averiguar el número de formas en que se pueden ordenar n números. Por ejemplo, dos números dicen que a y b se pueden pedir de 3 formas.

De forma similar, se pueden organizar 3 números de 13 maneras.

Descubrí que puedo resolver el problema usando la programación dinámica. Y aquí está lo que estoy pensando para tener capas que representen diferentes ordenamientos. Ex. a > b tiene dos capas y a = b tiene una sola capa y así sucesivamente. Para que pueda usarlo para fines posteriores como se hace en la programación dinámica. Pero no puedo escribir una relación de recurrencia para el mismo. ¿Puede alguien sugerirme cómo puedo escribir eso?

Answer 1

Supongamos f (n, k) = número de formas posibles por tener k desigualdad (y así NK-1 igualdad), por lo que: supone que tiene n-1 número, ahora quiere para agregar otro número y calcular f (n, k), entonces tenemos dos posibilidades lity:

1) Hay (k-1) desigualdades en esos (n-1) números, y hay (k + 1) (f (n-1, k-1)) formas de agregar n ' el número para que se agregue nueva desigualdad.

2) Hay k desigualdades en esos (n-1) números, y hay (k + 1) (f (n-1, k)) formas de sumar n-ésimo número sin desigualdad adicional.

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

y lo que quiere es la suma de ellos (de cero a n-1), el código de fuelle está en C# (solo probado para los casos simples), de hecho apenas calculamos el número de posibles formas no generar todas las formas ..

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

Honestamente creo que resolverlo mediante programación dinámica es como matar a la hormiga con una ametralladora.

Definitivamente debe utilizar combinatorics, porque no debería ser tan difícil.

Cuando no hay igualdad, su n! (permutación), entonces debe contar combinaciones (todos ntuplas iguales), por lo que es para 3

3! + 2 * (3 sobre 2) + (3 sobre 3) = 13

Answer 3

Los siguientes salidas C# programa, tanto el número de ordenamientos, y los propios ordenamientos:

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

Ejemplo de salida (para 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

He encontrado que el On-Line Encyclopedia of Integer Sequences es un gran recurso para problemas como este. Usted ha dado suficiente información para obtener la respuesta también. Claramente, para el caso degenerado de números cero, solo es posible realizar un pedido. Además, solo existe un pedido para un solo número. Para dos, dijiste que hay tres ordenamientos y para tres enteros hay trece. Busque 1,1,3,13 y el primer partido que aparece es this one, "Número de formas en que los competidores pueden clasificarse en una competencia, lo que permite la posibilidad de vínculos". Desde allí verá los primeros veinte resultados en esta secuencia y todo el contenido que la gente haya contribuido en la secuencia.Figura entre los demás es una solución recursiva en Mathematica (formateado y se expandió aquí una aclaración):

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

que se puede implementar fácilmente en otro idioma si lo prefiere.

Espero que esto ayude y que encuentre el OEIS útil en el futuro.