arrays - permutaciones - ¿Cómo saber si una matriz es una permutación en O(n)?
permutaciones y combinaciones (16)
Entrada: una matriz de solo lectura de N elementos que contienen valores enteros de 1 a N (¡algunos valores enteros pueden aparecer más de una vez!). Y una zona de memoria de un tamaño fijo (10, 100, 1000, etc., que no depende de N).
¿Cómo saber en O (n) si la matriz representa una permutación?
--Lo que logré hasta ahora (una respuesta demostró que esto no era bueno): -
- Uso el área de memoria limitada para almacenar la suma y el producto de la matriz.
- ¡Comparo la suma con N * (N + 1) / 2 y el producto con N!
Sé que si la condición (2) es verdadera, podría tener una permutación. Me pregunto si hay una forma de probar que la condición (2) es suficiente para saber si tengo una permutación. Hasta ahora no me he dado cuenta de esto ...
Aquí hay una prueba de que no se puede hacer:
Supongamos que por algún artificio no ha detectado duplicados en todas las celdas, excepto en la última. Entonces, el problema se reduce a verificar si esa última celda contiene un duplicado.
Si no tiene una representación estructurada del estado del problema hasta el momento, entonces se ve obligado a realizar una búsqueda lineal en toda la entrada anterior, para CADA celda. Es fácil ver cómo esto te deja con un algoritmo de tiempo cuadrático.
Ahora, supongamos a través de una estructura de datos inteligente que realmente sabes qué número esperas ver al final. Entonces, sin duda, ese conocimiento toma al menos suficientes bits para almacenar el número que buscas, ¿quizás una celda de memoria? Pero hay un segundo penúltimo número y un penúltimo subproblema: entonces debe representar de manera similar un conjunto de dos posibles números aún por ver. Esto ciertamente requiere más almacenamiento que la codificación solo para un número restante. Mediante una progresión de argumentos similares, el tamaño del estado debe crecer con el tamaño del problema, a menos que esté dispuesto a aceptar un peor caso de tiempo cuadrático.
Esta es la compensación de tiempo y espacio. Puede tener tiempo cuadrático y espacio constante, o tiempo lineal y espacio lineal. No puedes tener tiempo lineal y espacio constante.
Bien, esto es diferente, pero parece funcionar.
Ejecuté este programa de prueba (C #):
static void Main(string[] args) {
for (int j = 3; j < 100; j++) {
int x = 0;
for (int i = 1; i <= j; i++) {
x ^= i;
}
Console.WriteLine("j: " + j + "/tx: " + x + "/tj%4: " + (j % 4));
}
}
Breve explicación: x es el resultado de todos los XOR para una sola lista, i es el elemento en una lista particular, y j es el tamaño de la lista. Como todo lo que hago es XOR, el orden de los elementos no importa. Pero estoy mirando cómo se ven las permutaciones correctas cuando esto se aplica.
Si observa j% 4, puede hacer un cambio en ese valor y obtener algo como esto:
bool IsPermutation = false;
switch (j % 4) {
case 0:
IsPermutation = (x == j);
break;
case 1:
IsPermutation = (x == 1);
break;
case 2:
IsPermutation = (x == j + 1);
break;
case 3:
IsPermutation = (x == 0);
break;
}
Ahora reconozco que esto probablemente requiera un ajuste fino. No es 100%, pero es una buena manera fácil de comenzar. Tal vez con algunos pequeños controles que se ejecutan a lo largo del ciclo XOR, esto podría perfeccionarse. Intenta comenzar en algún lugar por allí.
Dependiendo de la cantidad de espacio que tenga, en relación con N, puede intentar usar hash y cubetas.
Es decir, itere sobre toda la lista, controle cada elemento y guárdelo en un cubo. Deberá encontrar una forma de reducir las colisiones de cubos de los hashes, pero ese es un problema resuelto.
Si un elemento intenta entrar en un cubo con un elemento idéntico, es una permutación.
Este tipo de solución sería O (N) al tocar cada elemento solo una vez.
Sin embargo, el problema con esto es si el espacio M es mayor que N o no. Si M> N, esta solución estará bien, pero si M <N, entonces no podrá resolver el problema con 100% de precisión.
Dudo que puedas probar eso;)
(1, 2, 4, 4, 4, 5, 7, 9, 9)
Creo que, en términos más generales, este problema no se puede resolver procesando los números en orden. Supongamos que está procesando los elementos en orden y está a medio camino de la matriz. Ahora el estado de su programa tiene que reflejar de alguna manera qué números ha encontrado hasta ahora. Esto requiere al menos O (n) bits para almacenar.
Es posible que pueda hacer esto en tiempo O(n) aleatorio y espacio constante al calcular el módulo sum(x_i) y product(x_i) un conjunto de diferentes constantes C elegidas al azar de tamaño O(n) . Esto básicamente te ayuda a resolver el problema de que el product(x_i) sea demasiado grande.
Sin embargo, todavía hay muchas preguntas abiertas, como si sum(x_i)=N(N+1)/2 y product(x_i)=N! son condiciones suficientes para garantizar una permutación, y ¿cuál es la probabilidad de que una no permutación genere un falso positivo (esperaría ~ 1 / C por cada C que intentas, pero tal vez no).
Esto es imposible de hacer en el espacio O (1), al menos con un algoritmo de escaneo único.
Prueba
Supongamos que ha procesado N / 2 de los N elementos. Asumiendo que la secuencia es una permutación, entonces, dado el estado del algoritmo, debería ser capaz de descubrir el conjunto de N / 2 elementos restantes. Si no puede descubrir los elementos restantes, entonces el algoritmo puede ser engañado al repetir algunos de los elementos antiguos.
Hay N elegir N / 2 posibles conjuntos restantes. Cada uno de ellos debe estar representado por un estado interno distinto del algoritmo, porque de lo contrario no se podrían descubrir los elementos restantes. Sin embargo, se necesita espacio logarítmico para almacenar estados X, por lo que se necesita espacio BigTheta (log (N elegir N / 2)) para almacenar N elegir N / 2 estados. Los valores crecen con N y, por lo tanto, el estado interno del algoritmo no puede caber en O (1) espacio.
Más prueba formal
Desea crear un programa P que, dados los últimos elementos N / 2 y el estado interno del algoritmo de espacio-tiempo-lineal-lineal después de haber procesado N / 2 elementos, determine si la secuencia completa es una permutación de 1. .NORTE. No hay límite de tiempo o espacio en este programa secundario.
Suponiendo que P existe, podemos crear un programa Q, tomando solo el estado interno del algoritmo de espacio-tiempo-constante lineal, que determina los elementos N / 2 finales necesarios de la secuencia (si se tratara de una permutación). Q funciona al pasar P cada posible N / 2 elementos finales y devolver el conjunto para el cual P devuelve verdadero.
Sin embargo, como Q tiene N elige N / 2 salidas posibles, debe tener al menos N elegir N / 2 entradas posibles. Eso significa que el estado interno del algoritmo original debe almacenar al menos N elegir N / 2 estados, que requieren BigTheta (log N elegir N / 2), que es mayor que el tamaño constante.
Por lo tanto, el algoritmo original, que tiene límites de tiempo y espacio, tampoco puede funcionar correctamente si tiene un estado interno de tamaño constante.
[Creo que esta idea puede generalizarse, pero pensar no está demostrando.]
Consecuencias
BigTheta (log (N elige N / 2)) es igual a BigTheta (N). Por lo tanto, solo usar una matriz booleana y marcar valores cuando los encuentre es (probablemente) óptimo para el espacio, y el tiempo óptimo también, ya que toma tiempo lineal.
Esto no va a funcionar debido a la complejidad que se da como una función de N en lugar de M, lo que implica que N >> M
Esta fue mi oportunidad, pero para que un filtro de floración sea útil, necesitas una gran M, en cuyo punto también puedes usar un simple intercambio de bits para algo como enteros
http://en.wikipedia.org/wiki/Bloom_filter
Para cada elemento de la matriz Ejecute las funciones k hash Verifique la inclusión en el filtro bloom Si está allí, hay una probabilidad de que haya visto el elemento antes. Si no lo está, agréguelo.
Cuando hayas terminado, puedes compararlo con los resultados de una matriz 1.N en orden, ya que solo te costará otra N.
Ahora bien, si no he puesto suficientes advertencias, no es 100%, o incluso cercano, ya que especificó complejidad en N, lo que implica que N >> M, por lo que fundamentalmente no funcionará como lo ha especificado.
Por cierto, la tasa de falsos positivos para un elemento individual debe ser e = 2 ^ (- m / (n * sqrt (2)))
Con qué monos te dará una idea de lo grande que M necesitaría ser para ser aceptable.
La solución Java a continuación responde la pregunta en parte. La complejidad del tiempo creo que es O (n). (Esta creencia se basa en el hecho de que la solución no contiene bucles anidados.) Acerca de la memoria: no estoy seguro. La pregunta aparece primero en solicitudes relevantes en google, por lo que probablemente pueda ser útil para alguien.
public static boolean isPermutation(int[] array) {
boolean result = true;
array = removeDuplicates(array);
int startValue = 1;
for (int i = 0; i < array.length; i++) {
if (startValue + i != array[i]){
return false;
}
}
return result;
}
public static int[] removeDuplicates(int[] input){
Arrays.sort(input);
List<Integer> result = new ArrayList<Integer>();
int current = input[0];
boolean found = false;
for (int i = 0; i < input.length; i++) {
if (current == input[i] && !found) {
found = true;
} else if (current != input[i]) {
result.add(current);
current = input[i];
found = false;
}
}
result.add(current);
int[] array = new int[result.size()];
for (int i = 0; i < array.length ; i ++){
array[i] = result.get(i);
}
return array;
}
public static void main (String ... args){
int[] input = new int[] { 4,2,3,4,1};
System.out.println(isPermutation(input));
//output true
input = new int[] { 4,2,4,1};
System.out.println(isPermutation(input));
//output false
}
La suma y el producto no garantizarán la respuesta correcta, ya que estos hash están sujetos a colisiones, es decir, diferentes entradas podrían producir resultados idénticos. Si desea un hash perfecto, un resultado de un solo número que realmente describa completamente la composición numérica de la matriz, podría ser el siguiente.
Imagine que para cualquier número i en el rango [1, N] puede producir un número primo único P(i) (por ejemplo, P(i) es el número primo i-ésimo). Ahora todo lo que necesita hacer es calcular el producto de todos los P(i) para todos los números en su matriz. El producto describirá completa y sin ambigüedades la composición de su matriz, sin tener en cuenta el orden de los valores en ella. Todo lo que necesita hacer es precalcular el valor "perfecto" (para una permutación) y compararlo con el resultado de una entrada dada :)
Por supuesto, el algoritmo de este tipo no satisface de inmediato los requisitos publicados. Pero al mismo tiempo es intuitivamente demasiado genérico: le permite detectar una permutación de absolutamente cualquier combinación numérica en una matriz. En su caso, necesita detectar una permutación de una combinación específica 1, 2, ..., N Tal vez esto de alguna manera se puede utilizar para simplificar las cosas ... Probablemente no.
Mira la siguiente solución. Usa O (1) espacio adicional . Altera la matriz durante el proceso de comprobación, pero la devuelve a su estado inicial al final.
La idea es:
- Compruebe si alguno de los elementos está fuera del rango [1, n] => O (n).
Revise los números en orden (todos ahora están seguros de estar en el rango [1, n]), y para cada número x (por ejemplo, 3):
- ir a la celda x''th (por ejemplo, a [3]), si es negativo, entonces alguien ya lo visitó antes que usted => No permutación. De lo contrario (a [3] es positivo), multiplíquelo por -1. => O (n).
- Repase la matriz y niegue todos los números negativos.
De esta forma, sabemos con certeza que todos los elementos están en el rango [1, n], y que no hay duplicados => La matriz es una permutación.
int is_permutation_linear(int a[], int n) {
int i, is_permutation = 1;
// Step 1.
for (i = 0; i < n; ++i) {
if (a[i] < 1 || a[i] > n) {
return 0;
}
}
// Step 2.
for (i = 0; i < n; ++i) {
if (a[abs(a[i]) - 1] < 0) {
is_permutation = 0;
break;
}
a[i] *= -1;
}
// Step 3.
for (i = 0; i < n; ++i) {
if (a[i] < 0) {
a[i] *= -1;
}
}
return is_permutation;
}
Aquí está el programa completo que lo prueba:
/*
* is_permutation_linear.c
*
* Created on: Dec 27, 2011
* Author: Anis
*/
#include <stdio.h>
int abs(int x) {
return x >= 0 ? x : -x;
}
int is_permutation_linear(int a[], int n) {
int i, is_permutation = 1;
for (i = 0; i < n; ++i) {
if (a[i] < 1 || a[i] > n) {
return 0;
}
}
for (i = 0; i < n; ++i) {
if (a[abs(a[i]) - 1] < 0) {
is_permutation = 0;
break;
}
a[abs(a[i]) - 1] *= -1;
}
for (i = 0; i < n; ++i) {
if (a[i] < 0) {
a[i] *= -1;
}
}
return is_permutation;
}
void print_array(int a[], int n) {
int i;
for (i = 0; i < n; i++) {
printf("%2d ", a[i]);
}
}
int main() {
int arrays[9][8] = { { 1, 2, 3, 4, 5, 6, 7, 8 },
{ 8, 6, 7, 2, 5, 4, 1, 3 },
{ 0, 1, 2, 3, 4, 5, 6, 7 },
{ 1, 1, 2, 3, 4, 5, 6, 7 },
{ 8, 7, 6, 5, 4, 3, 2, 1 },
{ 3, 5, 1, 6, 8, 4, 7, 2 },
{ 8, 3, 2, 1, 4, 5, 6, 7 },
{ 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 8, 4, 2, 1, 3, 5, 6 } };
int i;
for (i = 0; i < 9; i++) {
printf("array: ");
print_array(arrays[i], 8);
printf("is %spermutation./n",
is_permutation_linear(arrays[i], 8) ? "" : "not ");
printf("after: ");
print_array(arrays[i], 8);
printf("/n/n");
}
return 0;
}
Y su resultado:
array: 1 2 3 4 5 6 7 8 is permutation.
after: 1 2 3 4 5 6 7 8
array: 8 6 7 2 5 4 1 3 is permutation.
after: 8 6 7 2 5 4 1 3
array: 0 1 2 3 4 5 6 7 is not permutation.
after: 0 1 2 3 4 5 6 7
array: 1 1 2 3 4 5 6 7 is not permutation.
after: 1 1 2 3 4 5 6 7
array: 8 7 6 5 4 3 2 1 is permutation.
after: 8 7 6 5 4 3 2 1
array: 3 5 1 6 8 4 7 2 is permutation.
after: 3 5 1 6 8 4 7 2
array: 8 3 2 1 4 5 6 7 is permutation.
after: 8 3 2 1 4 5 6 7
array: 1 1 1 1 1 1 1 1 is not permutation.
after: 1 1 1 1 1 1 1 1
array: 1 8 4 2 1 3 5 6 is not permutation.
after: 1 8 4 2 1 3 5 6
No sé cómo hacerlo en O (N), o incluso si se puede hacer en O (N). Sé que se puede hacer en O (N log N) si (usa un apropiado) ordena y compara.
Dicho esto, hay muchas técnicas de O (N) que se pueden hacer para demostrar que una NO es una permutación de la otra.
- Verifique la duración. Si es desigual, obviamente no es una permutación.
- Crea una huella digital XOR. Si el valor de todos los elementos unidos por XOR juntos no coincide, entonces no puede ser una permutación. Sin embargo, un partido no sería concluyente.
- Encuentra la suma de todos los elementos. Aunque el resultado puede desbordarse, eso no debería ser una preocupación al hacer coincidir esta ''huella digital''. Sin embargo, si hiciera una suma de comprobación que implicara la multiplicación, el desbordamiento sería un problema.
Espero que esto ayude.
Primero, una razón teórica de la información por la cual esto puede ser posible. Podemos verificar trivialmente que los números en la matriz están dentro de límites en O (N) tiempo y O (1) espacio. Para especificar cualquier matriz de números dentro de límites se requiere N log N bits de información. Pero especificar una permutación requiere aproximadamente (N log N) - N bits de información (aproximación de Stirling). Por lo tanto, si pudiéramos adquirir N bits de información durante la prueba, podríamos conocer la respuesta. Esto es trivial en N tiempo (de hecho, con M espacio estático podemos fácilmente adquirir información de log M por paso, y bajo circunstancias especiales podemos adquirir información de log N ).
Por otro lado, solo almacenamos algo como M log N bits de información en nuestro espacio de almacenamiento estático, que es presumiblemente mucho menor que N , por lo que depende en gran medida de la forma de la superficie de decisión entre "permutación" y " no".
Creo que esto es casi posible, pero no del todo la configuración del problema. Creo que se supone que uno debe usar el truco del ciclismo (como en el enlace que Iulian mencionó), pero la suposición clave de tener una cola en la mano falla aquí porque puedes indexar el último elemento de la matriz con una permutación.
Soy muy poco escéptico de que haya una solución. Su problema parece ser muy similar a uno planteado hace varios años en la literatura matemática, con un resumen dado aquí ("The Duplicate Detection Problem", S. Kamal Abdali, 2003) que utiliza la detección de ciclos, la idea es la siguiente :
Si hay un duplicado, existe un número j entre 1 y N tal que lo siguiente llevaría a un bucle infinito:
x := j;
do
{
x := a[x];
}
while (x != j);
porque una permutación consiste en uno o más subconjuntos S de elementos distintos s 0 , s 1 , ... s k-1 donde s j = a [s j-1 ] para todos j entre 1 y k-1, y s 0 = a [s k-1 ], por lo que todos los elementos están involucrados en ciclos: uno de los duplicados no sería parte de dicho subconjunto.
por ejemplo, si la matriz = [2, 1, 4, 6, 8 , 7, 9, 3, 8]
luego, el elemento en negrita en la posición 5 es un duplicado porque todos los otros elementos forman ciclos: {2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 3}. Mientras que las matrices [2, 1, 4, 6, 5, 7, 9, 3, 8] y [2, 1, 4, 6, 3, 7, 9, 5, 8] son permutaciones válidas (con ciclos {2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 3, 5} y {2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 5 -> 3} respectivamente).
Abdali entra en una forma de encontrar duplicados. Básicamente, el siguiente algoritmo (usando el algoritmo de búsqueda de ciclos de Floyd ) funciona si te encuentras con uno de los duplicados en cuestión:
function is_duplicate(a, N, j)
{
/* assume we''ve already scanned the array to make sure all elements
are integers between 1 and N */
x1 := j;
x2 := j;
do
{
x1 := a[x1];
x2 := a[x2];
x2 := a[x2];
} while (x1 != x2);
/* stops when it finds a cycle; x2 has gone around it twice,
x1 has gone around it once.
If j is part of that cycle, both will be equal to j. */
return (x1 != j);
}
La dificultad es que no estoy seguro de que su problema como se indica coincida con el de su documento, y tampoco estoy seguro de si el método que describe se ejecuta en O (N) o usa una cantidad fija de espacio. Un posible contraejemplo es la siguiente matriz:
[3, 4, 5, 6, 7, 8, 9, 10, ... N-10, N-9, N-8, N-7, N-2, N-5, N-5, N- 3, N-5, N-1, N, 1, 2]
que es básicamente la permutación de identidad desplazada por 2, con los elementos [N-6, N-4 y N-2] reemplazados por [N-2, N-5, N-5]. Esto tiene la suma correcta (no el producto correcto, pero rechazo tomar el producto como posible método de detección ya que los requisitos de espacio para computar N! Con aritmética de precisión arbitraria son O (N) que viola el espíritu del "espacio de memoria fijo" requisito), y si intenta encontrar ciclos, obtendrá ciclos {3 -> 5 -> 7 -> 9 -> ... N-7 -> N-5 -> N-1} y {4 -> 6 -> 8 -> ... N-10 -> N-8 -> N-2 -> N -> 2}. El problema es que podría haber hasta N ciclos, (la permutación de identidad tiene N ciclos) tomando cada uno hasta O (N) para encontrar un duplicado, y usted debe seguir de alguna manera los ciclos que se han rastreado y los que no. Soy escéptico de que sea posible hacerlo en una cantidad fija de espacio. Pero tal vez lo es.
Este es un problema suficientemente pesado que vale la pena preguntar en mathoverflow.net (a pesar de que la mayoría de las veces se menciona mathoverflow.net en , es para problemas que son demasiado fáciles)
editar: pregunté en mathoverflow , hay una discusión interesante allí.
es una permutación si y solo si no hay valores duplicados en la matriz, debería ser fácil verificar que en O (N)
parece que se pide encontrar duplicados en la matriz con la máquina de pila.
parece imposible saber el historial completo de la pila, mientras extrae cada número y tiene un conocimiento limitado de los números que se extrajeron.
int solution(int A[], int N) {
int i,j,count=0, d=0, temp=0,max;
for(i=0;i<N-1;i++) {
for(j=0;j<N-i-1;j++) {
if(A[j]>A[j+1]) {
temp = A[j+1];
A[j+1] = A[j];
A[j] = temp;
}
}
}
max = A[N-1];
for(i=N-1;i>=0;i--) {
if(A[i]==max) {
count++;
}
else {
d++;
}
max = max-1;
}
if(d!=0) {
return 0;
}
else {
return 1;
}
}