Cuenta matrices que hacen conjuntos únicos

11

Esta pregunta tiene una configuración similar para encontrar una matriz que se ajuste a un conjunto de sumas, aunque es bastante diferente en sus objetivos.

Considere una variedad Ade longitud n. La matriz contiene solo enteros positivos. Por ejemplo A = (1,1,2,2). Definamos f(A)como el conjunto de sumas de todos los subconjuntos contiguos no vacíos de A. En este caso f(A) = {1,2,3,4,5,6}. Los pasos para producir f(A) son los siguientes:

Las submatrices de Ason (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Sus sumas respectivas son 1,1,2,2,2,3,4,4,5,6. El conjunto que obtienes de esta lista es por lo tanto {1,2,3,4,5,6}.

Llamamos a una matriz A única si no hay otra matriz Bde la misma longitud que f(A) = f(B), a excepción de la matriz Ainvertida. Como ejemplo, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6}pero no hay otra matriz de longitud 3que produzca el mismo conjunto de sumas.

Solo consideraremos matrices donde los elementos son un entero dado so s+1. Por ejemplo, si s=1las matrices solo contendrían 1y 2.

Tarea

La tarea, para un dado ny ses contar el número de matrices únicas de esa longitud. Puede suponer que sestá entre 1y 9.

No debe contar el reverso de una matriz ni la matriz misma.

Ejemplos

s = 1, la respuesta es siempre n+1.

s = 2, las respuestas que cuentan desde n = 1arriba son:

2,3,6,10,20,32,52,86

s = 8, las respuestas que cuentan desde n = 1arriba son:

2,3,6,10,20,36,68,130

Puntuación

Para un determinado n, su código debe generar la respuesta para todos los valores de sfrom 1a 9. Su puntaje es el valor más alto npara el cual esto se completa en un minuto.

Pruebas

Necesitaré ejecutar su código en mi máquina ubuntu, así que incluya las instrucciones más detalladas posibles sobre cómo compilar y ejecutar su código.

Tabla de clasificación

  • n = 24 por Anders Kaseorg en Rust (34 segundos)
  • n = 16 por Ourous en Clean (36 segundos)
  • n = 14 por JRowan en Common Lisp (49 segundos)
Anush
fuente
Entonces, si s = 8, entonces es una matriz de todas las combinaciones posibles de 8 y 9, ¿nada más?
JRowan
@JRowan No. No cuenta ninguna de esas matrices que tienen el mismo conjunto de sumas que alguna otra matriz.
Anush
Estoy un poco confundido sobre esta parte. Solo consideraremos matrices donde los elementos son un entero dado so s + 1. Por ejemplo, si s = 1, las matrices solo contendrían 1 y 2. Entonces, si n es 2 ys es 3, ¿cuáles serían las matrices para probar?
JRowan
¿Qué pasa con [3,3] y actualmente estoy eliminando el reverso de las listas, por ejemplo. [3,4] -> [4,3]
JRowan
2
@RosLuP En primer lugar, quería publicar eso en la otra pregunta , y en segundo lugar, [3, 5, 4] es un subconjunto pero no un subconjunto de [3, 5, 1, 4].
Anders Kaseorg

Respuestas:

5

Óxido , n ≈ 24

Requiere óxido nocturno para la reverse_bitscaracterística conveniente . Compilar rustc -O unique.rsy ejecutar con (por ejemplo) ./unique 24.

#![feature(reverse_bits)]
use std::{collections::HashMap, env, mem, process};

type T = u32;
const BITS: u32 = mem::size_of::<T>() as u32 * 8;

fn main() {
    let args = env::args().collect::<Vec<_>>();
    assert!(args.len() == 2);
    let n: u32 = args[1].parse().unwrap();
    assert!(n > 0);
    assert!(n <= BITS);
    let mut unique = (2..=9).map(|_| HashMap::new()).collect::<Vec<_>>();
    let mut sums = vec![0 as T; n as usize];
    for a in 0 as T..=!0 >> (BITS - n) {
        if a <= a.reverse_bits() >> (BITS - n) {
            for v in &mut sums {
                *v = 0;
            }
            for i in 0..n {
                let mut bit = 1;
                for j in i..n {
                    bit <<= a >> j & 1;
                    sums[(j - i) as usize] |= bit;
                }
            }
            for s in 2..=9 {
                let mut sums_s =
                    vec![0 as T; ((n + (n - 1) * s) / BITS + 1) as usize].into_boxed_slice();
                let mut pos = 0;
                let mut shift = 0;
                let mut lo = 0;
                let mut hi = 0;
                for &v in &sums {
                    lo |= v << shift;
                    if BITS - shift < n {
                        hi |= v >> (BITS - shift);
                    }
                    shift += s;
                    if shift >= BITS {
                        shift -= BITS;
                        sums_s[pos] = lo;
                        pos += 1;
                        lo = hi;
                        hi = 0;
                    }
                }
                if lo != 0 || hi != 0 {
                    sums_s[pos] = lo;
                    pos += 1;
                    if hi != 0 {
                        sums_s[pos] = hi;
                    }
                }
                unique[s as usize - 2]
                    .entry(sums_s)
                    .and_modify(|u| *u = false)
                    .or_insert(true);
            }
        }
    }
    let mut counts = vec![n + 1];
    counts.extend(
        unique
            .iter()
            .map(|m| m.values().map(|&u| u as T).sum::<T>())
            .collect::<Vec<_>>(),
    );
    println!("{:?}", counts);
    process::exit(0); // Avoid running destructors.
}
Anders Kaseorg
fuente
Esto es genial, gracias. Se completa para n = 25 en aproximadamente 90 segundos. Pero el problema principal es que usa el 70% de mis 8 GB de RAM.
Anush
De repente me he preocupado por algo. ¿Está comprobando que las matrices son únicas con respecto a todas las demás matrices posibles, o solo matrices con valores sy s+1en ellas?
Anush
@Anush Sí, cambié algo de uso de memoria por velocidad. Estoy contando matrices que son únicas con otras matrices con valores sy s + 1(dado que usted dijo que esas son las únicas matrices que consideraremos), aunque no es inmediatamente obvio si eso marcaría la diferencia.
Anders Kaseorg
1
Creo que tendré que resolver esto mañana. Las matrices 1,1,2,2 y 1,1,1,3 dan el conjunto de sumas 1,2,3,4,5,6. Sin embargo, el primero no es único entre las matrices con solo 1 y 2, por lo que estoy un poco confundido si hace la diferencia ahora.
Anush
2
@Anush Hace una diferencia: las sumas de [1, 2, 2, 2] son ​​únicas entre las matrices con 1 y 2 de longitud 4, pero iguales a las sumas de [1, 1, 2, 3].
Anders Kaseorg
2

SBCL común de Lisp, N = 14

función de llamada (goahead ns)

    (defun sub-lists(l m &optional(x 0)(y 0))
  (cond; ((and(= y (length l))(= x (length l)))nil)
        ((= y (length l))m)
        ((= x (length l))(sub-lists l m 0(1+ y)))
    (t (sub-lists l (cons(loop for a from x to (+ x y)

             when (and(nth (+ x y)l)(nth a l)(< (+ x y)(length l)))
                ;   while (nth a l)
             ;while(and(< (+ x y)(length l))(nth a l))
                    collect (nth a l))m) (1+ x)y))
    ))
(defun permutations(size elements)
  (if (zerop size)'(())
 (mapcan (lambda (p)
                    (map 'list (lambda (e)
                           (cons e p))
                         elements))
     (permutations (1- size) elements))))
(defun remove-reverse(l m)
  (cond ((endp l)m)
    ((member (reverse (first l))(rest l) :test #'equal)(remove-reverse (rest l)m))
    (t (remove-reverse (rest l)(cons (first l)m)))))
(defun main(n s)
  (let((l (remove-reverse (permutations n `(,s ,(1+ s)))nil)))

  (loop for x in l
     for j = (remove 'nil (sub-lists x nil))
       collect(sort (make-set(loop for y in j
        collect (apply '+ y))nil)#'<)
     )
  ))
(defun remove-dups(l m n)
  (cond ((endp l)n)
        ((member (first l) (rest l) :test #'equal)(remove-dups(rest l)(cons (first l) m) n))
    ((member (first l) m :test #'equal)(remove-dups(rest l)m n))
    (t(remove-dups (rest l) m (cons (first l) n))))

  )
(defun goahead(n s)
  (loop for a from 1 to s
  collect(length (remove-dups(main n a)nil nil))))
(defun make-set (L m)
  "Returns a set from a list. Duplicate elements are removed."
  (cond ((endp L) m)
    ((member (first L) (rest L)) (make-set (rest L)m))
    ( t (make-set (rest L)(cons (first l)m)))))

aquí están los tiempos de ejecución

CL-USER> (time (goahead 14 9))
Evaluation took:
  34.342 seconds of real time
  34.295000 seconds of total run time (34.103012 user, 0.191988 system)
  [ Run times consist of 0.263 seconds GC time, and 34.032 seconds non-GC time. ]
  99.86% CPU
  103,024,254,028 processor cycles
  1,473,099,744 bytes consed

(15 1047 4893 6864 7270 7324 7328 7328 7328)
CL-USER> (time (goahead 15 9))
Evaluation took:
  138.639 seconds of real time
  138.511089 seconds of total run time (137.923824 user, 0.587265 system)
  [ Run times consist of 0.630 seconds GC time, and 137.882 seconds non-GC time. ]
  99.91% CPU
  415,915,271,830 processor cycles
  3,453,394,576 bytes consed

(16 1502 8848 13336 14418 14578 14594 14594 14594)
JRowan
fuente
¿Cómo ejecuto esto? ¿Copio su código en un archivo y lo llamo de sbclalguna manera?
Anush
1
Uso emacs y slime, pero podría ponerlo en un archivo, por ejemplo, test.lisp y en sbcl prompt en su directorio (cargar "test.lisp") y luego llamar a la función como lo tengo en la parte inferior
JRowan
2

Limpiar

Ciertamente no es el enfoque más eficiente, pero estoy interesado en ver qué tan bien funciona un ingenuo filtro de valor.

Dicho esto, todavía hay un poco de mejora por hacer con este método.

module main
import StdEnv, Data.List, System.CommandLine

f l = sort (nub [sum t \\ i <- inits l, t <- tails i])

Start w
	# ([_:args], w) = getCommandLine w
	= case map toInt args of
		[n] = map (flip countUniques n) [1..9]
		_ = abort "Wrong number of arguments!"

countUniques 1 n = inc n
countUniques s n = length uniques
where
	lists = [[s + ((i >> p) bitand 1) \\ p <- [0..dec n]] \\ i <- [0..2^n-1]]
	pairs = sortBy (\(a,_) (b,_) = a < b) (zip (map f lists, lists))
	groups = map (snd o unzip) (groupBy (\(a,_) (b,_) = a == b) pairs)
	uniques = filter (\section = case section of [a, b] = a == reverse b; [_] = True; _ = False) groups

Coloque en un archivo llamado main.iclo cambie la línea superior a module <your_file_name_here>.

Compilar con clm -h 1500m -s 50m -fusion -t -IL Dynamics -IL StdEnv -IL Platform main.

Puede obtener la versión que TIO (y yo) usamos desde el enlace en el encabezado, o una más reciente desde aquí .

Οurous
fuente
No creo que este código dé la salida correcta. Lo probé con s = 8 y da [9,86,126,130,130,130,130,130,130]
Anush
@ Anush hmm Sé que lo probé. Veré si cambié algo entre eso y el publicado, dame unas horas y puedo hacerlo en mi descanso.
Novurous
@Anush ¿Por qué estás proporcionando s? En la pregunta que dice " Para un n dado , su código debe generar la respuesta para todos los valores de s del 1 al 9".
Precioso
1
Creo que eso es lo que llamas congelación cerebral de mi parte :) Ahora calcularé tu código.
Anush