¿Cómo puedo obtener algunas de todas las combinaciones posibles en R?

A veces quiero hacer una prueba exacta examinando todas las combinaciones posibles de los datos para construir una distribución empírica contra la cual pueda probar mis diferencias observadas entre medias. Para encontrar las posibles combinaciones, normalmente usaría la función combn. La función elegir me puede mostrar cuántas combinaciones posibles hay. Es muy fácil que el número de combinaciones sea tan grande que no sea posible almacenar el resultado de la función combn, por ejemplo, combn (28,14) requiere un vector de 2.1 Gb. Así que intenté escribir un objeto que pasara por la misma lógica que la función combinada para proporcionar los valores de una "pila" imaginaria, uno a la vez. Sin embargo, este método (como lo ejemplifiqué) es fácilmente 50 veces más lento que combinarlo en tamaños de combinación razonables,

¿Existe un mejor algoritmo para hacer este tipo de cosas que el algoritmo utilizado en combn? Específicamente, ¿hay alguna forma de generar y extraer la enésima combinación posible sin calcular todas las combinaciones anteriores?

r nonparametric combinatorics russellpierce
fuente

¿Alguien ha notado que la cantidad de preguntas que deberían estar en StackOverflow R se disparó aquí recientemente?

John

¿Por qué no hacer un muestreo aleatorio?

@John: Si te sientes así, discute el tema en meta.stats.stackexchange.com/questions/248/… , no necesitas ser sarcástico.

russellpierce

@mbq: el muestreo aleatorio proporcionará rápidamente una aproximación razonable, especialmente con datos bien comportados. Sin embargo, especifiqué que mi objetivo era una prueba exacta.

russellpierce

@drknexus Por eso fue un comentario, no una respuesta.

Respuestas:

Si desea cambiar la velocidad de procesamiento por la memoria (lo cual creo que hace), le sugiero el siguiente algoritmo:

Configure un bucle de 1 a N Elija K, indexado por i
Cada i puede considerarse un índice de una combinación , decodificar como tal
Use la combinación para realizar su estadística de prueba, almacenar el resultado, descartar la combinación
Repetir

Esto le dará todas las combinaciones posibles de N Elija K sin tener que crearlas explícitamente. Tengo un código para hacer esto en R si lo desea (puede enviarme un correo electrónico a mark dot m period fredrickson at-symbol gmail dot com).

Mark M. Fredrickson
fuente

Aquí hay una publicación con el código y algunas ilustraciones: markmfredrickson.com/thoughts/2010-08-06-combinadics-in-r.html

Mark M. Fredrickson

Estoy aceptando esta respuesta porque resuelve (lo que creo) es el más difícil de los problemas para los que estaba buscando una solución: elegir una combinación particular sin calcular los valores anteriores. Desafortunadamente, todavía es muy lento. Tal vez como se menciona aquí y en otros lugares, una búsqueda binaria ayudaría a acelerar las cosas. Quizás el mejor enfoque es tener un hilo que genere las combinaciones paso a paso como en la respuesta de mbq y otro hilo que las lea y las pruebe.

russellpierce

Generar combinaciones es bastante fácil, vea por ejemplo esto ; escriba este código en R y luego procese cada combinación a la vez que aparece.

fuente

¿Pero esto hará frente a combinaciones muy grandes?

csgillespie

@csgillespie Bueno, creo que sí, funciona in situ , por lo que solo se almacena una combinación en la memoria a la vez, y los resultados de la simulación también se pueden agregar para eliminar la necesidad de almacenarlos. Por supuesto, esto funcionará terriblemente largo, pero las búsquedas exhaustivas generalmente lo hacen. Para la velocidad, podría escribirse en C, pero luego junto con la parte de simulación, que probablemente sea mucho más lenta que un paso de generador.

Eso se ve casi idéntico a cómo la función combn de R ya está haciendo las cosas. Escribí una versión de combn que elimina combinaciones de la pila de una en una, y como dice mbq porque solo almacena una combinación en la memoria a la vez, puede manejar combinaciones muy grandes. El problema con hacerlo en R es que hacer un enfoque paso a paso en una función generalmente implica leer las variables de estado en la función, manipularlas y luego almacenarlas de nuevo en global, lo que parece ralentizar todo / forma / abajo.

russellpierce