obteniendo todos los vectores de una longitud determinada y con con $+-1$ entradas de una determinada

Question

Podemos "viajar" por todo el espacio vectorial $V =GF(2)^n$ haciendo lo siguiente

(a) elegir un polinomio primitivo $P(t)$ de grado $n$ en $GF(2)$ .

(b) vector de cambio $X = (x_1, \ldots,x_{n-1}) \in V$ en el vector $Y = (y_1, \ldots, y_{n-1}) \in V$ .

(c) repetir hasta que $V$ se agota (2^n veces)

donde

$y_1+y_2z+ \cdots + y_nz^{n-1} = z(x_1+x_2z+ \cdots + x_nz^{n-1})$

y $z$ es un cero de $P$ es decir, $P(z)=0.$

Quiero hacer lo mismo con vectores integrales que contengan sólo 1 y -1

Es decir: "viajar" por todos los vectores posibles $(r_1, \ldots, r_{n-1})$

con $r_i^2=1$

¿Cómo hacer eso?

Hago algunos intentos sin éxito...

motivo de la pregunta: Sólo dispongo de un tiempo limitado en el ordenador ((cinco días por trabajo, dos trabajos permitidos)) y necesito probar algunos cálculos en todos esos vectores con un tamaño moderado. $n$

el bucle:

de r_1=-1 a 1 por 2 do;

de r_2=-1 a 1 por 2 hacer

$\cdots$

de r_{n-1}=-1 a 1 por 2 do;

no "encajan" en mi tiempo permitido.

siguiente sugerencia (gracias) consideremos lo siguiente:

Necesito examinar cada uno de los $2^n$ vectores.

Para encajar el tiempo permitido basta con romper el $2^n$ ¡en partes más pequeñas y aplicar a cada una de ellas el método que pido aquí !

Lo intenté:

(a) $r_i \in \{1,1\}$ ir a $si=(r_i+1)/2$ en $\{0,1\}$

(b) aplicar la idea con el polinomio primitivo, a la $s_i$ 's

(Por lo que se ve obligado a tomar alguna reducción modulo $2$ en algunas coordenadas)

(c) recuperar $R_j$ el nuevo $r_j$ , por $R_j=2s_j1$

para que desde el vector

$(r_1,…,r_n)$ obtenemos un nuevo vector $(R_1,…,R_n)$

y aplicando esta $2^n$ veces deberíamos (con suerte) obtener todos los $2^n$ vectores

pero esto NO funciona desde que terminé, por ejemplo, al ciclo

$(1,1,…,1)$ que va a sí mismo indefinidamente

En otras palabras: ¿Puedo escribir estos $2^n$ vectores como una secuencia

$v_1,…,v_{2^n}$ de tal manera

que puedo con un simple cálculo algebraico,

(similar al uso del polinomio primitivo en caso de que los vectores estén en $GF(2)^n$ ))

obtener el vector

$v_k$ del vector $v_{k1}$

empezando por cualquier vector fijo

$v_1$

???

Answer 1

Hay como $2^n$ de estos vectores. Si "necesita probar algunos cálculos en todos esos vectores" entonces, a menos que pueda factorizar algo de su cálculo, necesitará una cantidad de tiempo aproximadamente proporcional a $(2^n) \times$ (tiempo que se tarda en hacer cada cálculo).

Answer 2

Ver nueva versión editada de la pregunta

Answer 3

Simplemente represente cada vector como un entero binario:

$v_0 = "0 0 0 ... 0 0 0" = b_{n-1} b_{n-2}... b_2 b_1 b_0 = 0$

por lo que la secuencia de dígitos binarios que representa $i$ es un número decimal $d$

$$d = \sum_{j=0}^{j=n-1} b_j \cdot 2^{j}$$

Dada dicha representación binaria, se pueden transformar los dígitos binarios en los coeficientes mediante el mapeo $0 \to -1$ y $1 \to 1$

$b_j = 0 \to r_j = (-1)$ y

$b_j = 1 \to r_j = (+1)$

Entonces, dada una $v_j$ como un dígito binario, generar $v_{j+1}$ añadiendo $1$ a la representación binaria.

No hay ningún atajo para evitar tener que probar cada uno de los $2^n$ posibilidades, por lo que esto no hace que sus cálculos generales sean más rápidos. Sólo facilita la generación de los dígitos binarios.

Una forma más sencilla es iterar su índice como un entero (llamarlo $z$ ) de $0$ a $n-1$ y generar la representación binaria de cada $z$ . Hay muchas formas de hacerlo rápidamente que puedes encontrar con simples búsquedas en internet o preguntando en stackexchange.com