Eliminación de cada 'kth' persona de un círculo. Encuentre la última persona restante

Question

Como parte de una solicitud de empleo reciente, se me pidió que codificara una solución a este problema.

Dada,

• n = número de personas de pie en un círculo.
• k = número de personas a contar de nuevo cada vez

Cada persona se le da un identificador único (incremento). Comenzando con la primera persona (la identificación más baja), empiezan a contar de 1 a k.

La persona en k se retira y el círculo se cierra. La siguiente persona restante (siguiendo a la persona eliminada) reanuda el conteo en 1. Este proceso se repite hasta que solo queda una persona, el ganador.

La solución debe proporcionar:

• el id de cada persona en el orden en que se retiran del círculo
• el id del ganador.

limitaciones de rendimiento:

• usar la menor cantidad de memoria posible.
• Haga que la solución se ejecute lo más rápido posible.

Recordé hacer algo similar en mi curso de CS desde hace años, pero no pude recordar los detalles en el momento de esta prueba. Ahora me doy cuenta de que es un problema clásico bien conocido con múltiples soluciones. (No voy a mencionarlo por su nombre ya que algunos pueden simplemente 'wikipedia' una respuesta).

Ya presenté mi solución, así que no estoy buscando gente que me la responda. Lo proporcionaré un poco más tarde una vez/si otros han proporcionado algunas respuestas.

Mi objetivo principal al hacer esta pregunta es ver cómo mi solución se compara con otras según los requisitos y las limitaciones.

(Tenga en cuenta los requisitos de cuidado ya que creo que pueden invalidar algunas de las soluciones 'clásicas'.)

Answer 1

Ésta es mi solución, codificado en C#. ¿Qué podría mejorarse?

public class Person 
{ 
    public Person(int n) 
    { 
     Number = n; 
    } 

    public int Number { get; private set; } 
} 


static void Main(string[] args) 
{ 
    int n = 10; int k = 4; 
    var circle = new List<Person>(); 

    for (int i = 1; i <= n; i++) 
    { 
     circle.Add(new Person(i)); 
    } 

    var index = 0; 
    while (circle.Count > 1) 
    { 
     index = (index + k - 1) % circle.Count; 
     var person = circle[index]; 
     circle.RemoveAt(index); 
     Console.WriteLine("Removed {0}", person.Number); 
    } 
    Console.ReadLine(); 
} 
     Console.WriteLine("Winner is {0}", circle[0].Number); 

Answer 2

Puede hacerlo utilizando una matriz boolean.

Aquí es un pseudo código:

Let alive ser una matriz de tamaño booleanN. Si alive[i] es true, entonces ith persona está viva o muerta. Inicialmente es true por cada 1>=i<=N
Sea numAlive el número de personas con vida. Así que numAlive = N al inicio.

i = 1 # Counting starts from 1st person. 
count = 0; 

# keep looping till we've more than 1 persons. 
while numAlive > 1 do 

if alive[i] 
    count++ 
end-if 

# time to kill ? 
if count == K 
    print Person i killed 
    numAlive -- 
    alive[i] = false 
    count = 0 
end-if 

i = (i%N)+1 # Counting starts from next person. 

end-while 

# Find the only alive person who is the winner. 
while alive[i] != true do 
i = (i%N)+1 
end-while 
print Person i is the winner 

La solución anterior es el espacio eficiente, pero no eficiente en el tiempo como los muertos están siendo revisados.

Para que sea más eficiente del tiempo sabia que puede hacer uso de una lista enlazada circular . Cada vez que matas a una persona, borras un nodo de la lista. Continúa hasta que se deja un solo nodo en la lista.

Answer 3

Aquí está mi respuesta en C#, tal como se envió. Siéntase libre de criticar, reírse de, ridiculizar, etc;)

public static IEnumerable<int> Move(int n, int k) 
{ 
    // Use an Iterator block to 'yield return' one item at a time. 

    int children = n; 
    int childrenToSkip = k - 1; 

    LinkedList<int> linkedList = new LinkedList<int>(); 

    // Set up the linked list with children IDs 
    for (int i = 0; i < children; i++) 
    { 
     linkedList.AddLast(i); 
    } 

    LinkedListNode<int> currentNode = linkedList.First; 

    while (true) 
    { 
     // Skip over children by traversing forward 
     for (int skipped = 0; skipped < childrenToSkip; skipped++) 
     { 
      currentNode = currentNode.Next; 
      if (currentNode == null) currentNode = linkedList.First; 
     } 

     // Store the next node of the node to be removed. 
     LinkedListNode<int> nextNode = currentNode.Next; 

     // Return ID of the removed child to caller 
     yield return currentNode.Value; 

     linkedList.Remove(currentNode); 

     // Start again from the next node 
     currentNode = nextNode; 
     if (currentNode== null) currentNode = linkedList.First; 

     // Only one node left, the winner 
     if (linkedList.Count == 1) break; 
    } 

    // Finally return the ID of the winner 
    yield return currentNode.Value; 
} 

Answer 4

En esencia, el mismo que la respuesta de Ash, pero con una lista enlazada de encargo:

using System; 
using System.Linq; 

namespace Circle 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      Circle(20, 3); 
     } 

     static void Circle(int k, int n) 
     { 
      // circle is a linked list representing the circle. 
      // Each element contains the index of the next member 
      // of the circle. 
      int[] circle = Enumerable.Range(1, k).ToArray(); 
      circle[k - 1] = 0; // Member 0 follows member k-1 

      int prev = -1; // Used for tracking the previous member so we can delete a member from the list 
      int curr = 0; // The member we're currently inspecting 
      for (int i = 0; i < k; i++) // There are k members to remove from the circle 
      { 
       // Skip over n members 
       for (int j = 0; j < n; j++) 
       { 
        prev = curr; 
        curr = circle[curr]; 
       } 

       Console.WriteLine(curr); 
       circle[prev] = circle[curr]; // Delete the nth member 
       curr = prev; // Start counting again from the previous member 
      } 
     } 
    } 
} 

Answer 5

El problema de la determinación de la persona de orden k 'es llamado el problema de Josefo. Armin Shams-Baragh de la Universidad de Mashhad de Ferdowsi publicó algunas fórmulas para el problema de Josefo y la versión extendida de la misma. El artículo está disponible en: http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf

Answer 6

Aquí es una solución en Clojure:

(ns kthperson.core 
    (:use clojure.set)) 


(defn get-winner-and-losers [number-of-people hops] 
    (loop [people (range 1 (inc number-of-people)) 
     losers [] 
     last-scan-start-index (dec hops)] 
    (if (= 1 (count people)) 
     {:winner (first people) :losers losers} 
     (let [people-to-filter (subvec (vec people) last-scan-start-index) 
      additional-losers (take-nth hops people-to-filter) 
      remaining-people (difference (set people) 
             (set additional-losers)) 
      new-losers (concat losers additional-losers) 
      index-of-last-removed-person (* hops (count additional-losers))] 
     (recur remaining-people 
       new-losers 
       (mod last-scan-start-index (count people-to-filter))))))) 

Explicación:

• empezar un bucle, con una colección de personas 1..n

• si solo queda una persona, ellos son los ganadores y les devolvemos su identificación, así como los ID de los perdedores (en orden de em perder)

• calculamos perdedores adicionales en cada bucle/reaparecer por el acaparamiento de cada N personas en la lista restante de los posibles ganadores

• una nueva lista más corta de los posibles ganadores se determina mediante la eliminación de la perdedores adicionales de los ganadores potenciales previamente calculados.

• enjuague & repetición (usando el módulo para determinar dónde en la lista de permanecer a la gente a empezar a contar la siguiente ronda de tiempo)

Answer 7

Manuel González notó correctamente que esta es la forma general de la famosa Josephus problem.

Si solo estamos interesados ​​en el superviviente f (N, K) de un círculo de tamaño N y saltos de tamaño K, podemos resolverlo con un bucle de programación dinámica muy simple (en tiempo lineal y memoria constante) .Tenga en cuenta que los identificadores empiezan desde 0:

int remaining(int n, int k) { 
    int r = 0; 
    for (int i = 2; i <= n; i++) 
     r = (r + k) % i; 

    return r; 
} 

Se basa en la siguiente relación de recurrencia:

f (N, K) = (f (N-1, K) + K) mod N

Esta relación se puede explicar simulando el proceso de eliminación, y después de cada eliminación reasigna nuevos identificadores comenzando desde 0. Los índices antiguos son los nuevos con un desplazamiento circular de k posiciones. Para una explicación más detallada de esta fórmula, vea http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf.

Sé que OP pide todos los índices de los artículos eliminados en el orden correcto. Sin embargo, creo que la información anterior también se puede usar para resolver esto.

Answer 8

Esta es una variante de Josephus problem.

Las soluciones generales se describen here.

Las soluciones en Perl, Ruby y Python se proporcionan here. A continuación se proporciona una solución simple en C que usa un circular doubly-linked list para representar al círculo de personas. Sin embargo, ninguna de estas soluciones identifica la posición de cada persona a medida que se eliminan.

#include <stdio.h> 
#include <stdlib.h> 

/* remove every k-th soldier from a circle of n */ 
#define n 40 
#define k 3 

struct man { 
    int pos; 
    struct man *next; 
    struct man *prev; 
}; 

int main(int argc, char *argv[]) 
{ 
    /* initialize the circle of n soldiers */ 
    struct man *head = (struct man *) malloc(sizeof(struct man)); 
    struct man *curr; 
    int i; 
    curr = head; 
    for (i = 1; i < n; ++i) { 
     curr->pos = i; 
     curr->next = (struct man *) malloc(sizeof(struct man)); 
     curr->next->prev = curr; 
     curr = curr->next; 
    } 
    curr->pos = n; 
    curr->next = head; 
    curr->next->prev = curr; 

    /* remove every k-th */ 
    while (curr->next != curr) { 
     for (i = 0; i < k; ++i) { 
      curr = curr->next; 
     } 
     curr->prev->next = curr->next; 
     curr->next->prev = curr->prev; 
    } 

    /* announce last person standing */ 
    printf("Last person standing: #%d.\n", curr->pos); 
    return 0; 
}