Determine si un símbolo es parte de la i-ésima combinación nCr
UPDATE: La combinación y la clasificación fueron eventualmente lo que necesitaba. Los siguientes enlaces ayudaron mucho:
http: //msdn.microsoft.com/en-us/library/aa289166 (v = vs.71) .aspx
http: //www.codeproject.com/Articles/21335/Combinations-in-C-Part-
El problem
Dada una lista de N símbolos, digamos {0,1,2,3,4 ...}
Y combinaciones de NCr de estos
p.ej. NC3 generará:
0 1 2
0 1 3
0 1 4
...
...
1 2 3
1 2 4
etc...
Para la combinación i-ésima (i = [1 .. NCr]) quiero determinar si un símbolo (s) es parte de ella.
Func (N, r, i, s) = Verdadero / Falso o 0/1
p.ej. Continuando desde arriba La primera combinación contiene 0 1 2 pero no 3
F(N,3,1,"0") = TRUE
F(N,3,1,"1") = TRUE
F(N,3,1,"2") = TRUE
F(N,3,1,"3") = FALSE
Enfoques actuales y tibits que podrían ayudar o estar relacionados.
Relación con las matrices Para r = 2 ej. 4C2 las combinaciones son la mitad superior (o inferior) de una matriz 2D
1,2 1,3 1,4
----2,3 2,4
--------3,4
Para r = 3 es la esquina de una matriz 3D o cubo para r = 4 Es la "esquina" de una matriz 4D y así sucesivamente.
Otra relación
Idealmente, la solución sería de una forma similar a la respuesta a esto:Calcular combinación basada en la posición
La enésima combinación en la lista de combinaciones de longitud r (con la repetición permitida), el i-ésimo símbolo se puede calcular
Utilizando la división de enteros y el resto:
n / r ^ i% r = (0 para el 0 ° símbolo, 1 para el 1 ° símbolo ... etc.)
eg para el sexto peine de 3 símbolos, el 0º primer y segundo símbolos son:
i = 0 => 6 / 3^0 % 3 = 0
i = 1 => 6 / 3^1 % 3 = 2
i = 2 => 6 / 3^2 % 3 = 0
El sexto peine sería 0 2 0
Necesito algo similar, pero no se permite la reproducción.
Gracias por seguir esta pregunta hasta aquí:]
Kevin.