Hitung array yang membuat set unik

11

Pertanyaan ini memiliki susunan yang mirip dengan Find a array yang sesuai dengan jumlah penjumlahan meskipun sangat berbeda dalam tujuannya.

Pertimbangkan Apanjang array n. Array hanya berisi bilangan bulat positif. Sebagai contoh A = (1,1,2,2). Mari kita definisikan f(A)sebagai himpunan jumlah semua sub-susunan berdekatan yang tidak kosong dari A. Dalam hal ini f(A) = {1,2,3,4,5,6}. Langkah-langkah untuk menghasilkan f(A) adalah sebagai berikut:

Subarrays dari Aadalah (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Jumlah masing-masing adalah 1,1,2,2,2,3,4,4,5,6. Karenanya, set yang Anda dapatkan dari daftar ini {1,2,3,4,5,6}.

Kami memanggil array A unik jika tidak ada array lain Bdengan panjang yang sama sehingga f(A) = f(B), kecuali untuk array Aterbalik. Sebagai contoh, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6}tetapi tidak ada array panjang 3yang menghasilkan jumlah penjumlahan yang sama.

Kami hanya akan mempertimbangkan array di mana elemen-elemennya adalah bilangan bulat yang diberikan satau s+1. Misal jika s=1array hanya berisi 1dan 2.

Tugas

Tugas, untuk yang diberikan ndan suntuk menghitung jumlah array unik dengan panjang itu. Anda dapat berasumsi bahwa itu sadalah antara 1dan 9.

Anda seharusnya tidak menghitung kebalikan dari array serta array itu sendiri.

Contohnya

s = 1, jawabannya selalu n+1.

s = 2, jawaban yang dihitung dari n = 1atas adalah:

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

s = 8, jawaban yang dihitung dari n = 1atas adalah:

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

Skor

Untuk diberikan n, kode Anda harus menampilkan jawaban untuk semua nilai smulai dari 1hingga 9. Skor Anda adalah nilai tertinggi nyang menyelesaikannya dalam satu menit.

Pengujian

Saya perlu menjalankan kode Anda di mesin ubuntu saya, jadi harap sertakan instruksi sedetail mungkin untuk cara mengkompilasi dan menjalankan kode Anda.

Papan peringkat

  • n = 24 oleh Anders Kaseorg di Rust (34 detik)
  • n = 16 oleh Ourous in Clean (36 detik)
  • n = 14 oleh JRowan dalam Common Lisp (49 detik)
Anush
sumber
Jadi jika s = 8 maka array dari semua kemungkinan kombinasi 8 dan 9, tidak ada yang lain?
JRowan
@JRowan No. Anda tidak menghitung array yang memiliki jumlah penjumlahan yang sama dengan array lainnya.
Anush
Bagian ini saya sedikit bingung tentang Kami hanya akan mempertimbangkan array di mana elemen-elemennya adalah bilangan bulat s atau s +1. Misalkan jika s = 1 array hanya akan berisi 1 dan 2. Jadi jika n adalah 2 dan s adalah 3 array yang akan diuji?
JRowan
bagaimana dengan [3,3] dan saya sedang menghapus kebalikan dari daftar, mis. [3,4] -> [4,3]
JRowan
2
@RosLuP Pertama, Anda bermaksud memposting itu pada pertanyaan lain , dan kedua, [3, 5, 4] adalah himpunan bagian tetapi bukan subarray [3, 5, 1, 4].
Anders Kaseorg

Jawaban:

5

Karat , n ≈ 24

Membutuhkan Karat malam hari untuk reverse_bitsfitur yang nyaman . Kompilasi dengan rustc -O unique.rsdan jalankan dengan (misalnya) ./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
sumber
Ini bagus, terima kasih. Itu selesai untuk n = 25 dalam waktu sekitar 90 detik. Tetapi masalah utama adalah bahwa ia menggunakan 70% dari 8GB RAM saya.
Anush
Tiba-tiba saya khawatir tentang sesuatu. Apakah Anda memeriksa bahwa array itu unik berkenaan dengan semua array lain yang mungkin, atau hanya array dengan nilai sdan s+1di dalamnya?
Anush
@Anush Ya, saya menukar beberapa penggunaan memori untuk kecepatan. Saya menghitung array yang unik dengan array lain dengan nilai-nilai sdan s + 1(karena Anda mengatakan itu adalah satu-satunya array yang akan kita pertimbangkan), meskipun tidak segera jelas apakah itu akan membuat perbedaan.
Anders Kaseorg
1
Saya pikir saya perlu menyelesaikan ini besok. Array 1,1,2,2 dan 1,1,1,3 keduanya memberikan set jumlah 1,2,3,4,5,6. Namun yang pertama tidak unik di antara array dengan hanya 1 dan 2 jadi saya sedikit bingung jika itu membuat perbedaan sekarang.
Anush
2
@Anush Itu memang membuat perbedaan: jumlah [1, 2, 2, 2] unik di antara array dengan 1 dan 2 dengan panjang 4, tetapi sama dengan jumlah [1, 1, 2, 3].
Anders Kaseorg
2

Lisp umum SBCL, N = 14

fungsi panggilan (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)))))

di sini adalah waktu menjalankan

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
sumber
Bagaimana saya menjalankan ini? Apakah saya menyalin kode Anda ke file dan memanggilnya sbclentah bagaimana?
Anush
1
Saya menggunakan emacs dan slime tetapi Anda bisa memasukkannya ke dalam file say test.lisp dan di sbcl prompt pada panggilan direktori Anda (muat "test.lisp") dan kemudian panggil fungsi tersebut bagaimana saya memilikinya di bagian bawah
JRowan
2

Bersih

Tentu saja bukan pendekatan yang paling efisien, tapi saya tertarik melihat seberapa baik filter nilai-naif tidak.

Yang mengatakan, masih ada sedikit perbaikan yang harus dilakukan menggunakan metode ini.

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

Tempatkan dalam file bernama main.icl, atau ubah baris teratas menjadi module <your_file_name_here>.

Kompilasi dengan clm -h 1500m -s 50m -fusion -t -IL Dynamics -IL StdEnv -IL Platform main.

Anda bisa mendapatkan versi TIO (dan saya sendiri) gunakan dari tautan di tajuk, atau yang lebih baru dari sini .

Suram
sumber
Saya tidak berpikir kode ini memberikan output yang tepat. Saya mencobanya dengan s = 8 dan memberi [9,86.126.130.130.130.130.130.130]
Anush
@ Anush hmm aku tahu aku mengujinya. Saya akan melihat apakah saya mengubah apa pun antara itu dan yang diposting, beri saya beberapa jam dan saya bisa melakukannya saat istirahat.
Surous
@Anush Mengapa Anda menyediakan s? Dalam pertanyaan Anda menyatakan " Untuk n yang diberikan , kode Anda harus menampilkan jawaban untuk semua nilai s dari 1 hingga 9."
Surous
1
Saya pikir itulah yang Anda sebut pembekuan otak pada bagian saya :) Saya akan mengatur waktu kode Anda sekarang.
Anush