# Count arrays that make unique sets

This question has a similar set up to Find an array that fits a set of sums although is quite different in its goals.

Consider an array A of length n. The array contains only positive integers. For example A = (1,1,2,2). Let us define f(A) as the set of sums of all the non-empty contiguous subarrays of A. In this case f(A) = {1,2,3,4,5,6}. The steps to produce f(A) are as follows:

The subarrays of A are (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Their respective sums are 1,1,2,2,2,3,4,4,5,6. The set you get from this list is therefore {1,2,3,4,5,6}.

We call an array A unique if there is no other array B of the same length such that f(A) = f(B), except for the array A reversed. As an example, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6} but there is no other array of length 3 that produces the same set of sums.

We will only consider arrays where the elements are either a given integer s or s+1. E.g. if s=1 the arrays would only contain 1 and 2.

The task, for a given n and s is to count the number of unique arrays of that length. You can assume that s is between 1 and 9.

You should not count the reverse of an array as well as the array itself.

Examples

s = 1, the answer is always n+1.

s = 2, the answers counting from n = 1 up are:

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


s = 8, the answers counting from n = 1 up are:

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


Score

For a given n, your code should output the answer for all values of s from 1 to 9. Your score is the highest value of n for which this completes in one minute.

Testing

I will need to run your code on my ubuntu machine so please include as detailed instructions as possible for how to compile and run your code.

• n = 24 by Anders Kaseorg in Rust (34 seconds)
• n = 16 by Ourous in Clean (36 seconds)
• n = 14 by JRowan in Common Lisp (49 seconds)
• So if s=8 then its an array of all possible combinations of 8 and 9, nothing else? – JRowan Oct 24 '18 at 17:22
• @JRowan No. You don't count any of those arrays that have the same set of sums as some other array. – Anush Oct 24 '18 at 18:06
• This part i am a little confused about We will only consider arrays where the elements are either a given integer s or s+1. E.g. if s=1 the arrays would only contain 1 and 2. So if n is 2 and s is 3 what would the arrays to test be? – JRowan Oct 24 '18 at 18:21
• what about [3,3] and im currently removing the reverse of the lists eg. [3,4]->[4,3] – JRowan Oct 24 '18 at 18:27
• @RosLuP Firstly, you meant to post that on the other question, and secondly, [3, 5, 4] is a subset but not a subarray of [3, 5, 1, 4]. – Anders Kaseorg Oct 25 '18 at 23:17

# Rust, n ≈ 24

Requires nightly Rust for the convenient reverse_bits feature. Compile with rustc -O unique.rs and run with (e.g.) ./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.
}

• This is great, thank you. It completes for n = 25 in about 90 seconds. But the main problem is that it uses 70% of my 8GB of RAM. – Anush Oct 21 '18 at 18:14
• I have suddenly got worried about something. Are you checking that the arrays are unique with respect to all other possible arrays, or just arrays with values s and s+1 in them? – Anush Oct 21 '18 at 18:59
• @Anush Yes, I traded some memory usage for speed. I’m counting arrays that are unique w.r.t. other arrays with values s and s + 1 (since you said those are the only arrays we will consider), although it’s not immediately obvious whether that would make a difference. – Anders Kaseorg Oct 21 '18 at 21:43
• I think I will need to work this out tomorrow. The arrays 1,1,2,2 and 1,1,1,3 both give the set of sums 1,2,3,4,5,6. However the former is not unique amongst arrays with only 1 and 2 so I am a little confused if it makes a difference now. – Anush Oct 21 '18 at 21:47
• @Anush It does make a difference: the sums of [1, 2, 2, 2] are unique among arrays with 1 and 2 of length 4, but equal to the sums of [1, 1, 2, 3]. – Anders Kaseorg Oct 21 '18 at 21:56

Common Lisp SBCL, N = 14

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

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


here is the run times

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)
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)

• How do I run this? Do I copy your code into a file and call it from sbcl somehow? – Anush Nov 6 '18 at 20:47
• I use emacs and slime but you could put it in a file say test.lisp and in sbcl promp at your directory call (load "test.lisp") and then call the function how i have it at the bottom – JRowan Nov 6 '18 at 20:53

# Clean

Certainly not the most efficient approach, but I'm interested in seeing how well a naive by-value filter does.

That said, there's still a bit of improvement to be made using this method.

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


Place in a file named main.icl, or change the top line to module <your_file_name_here>.

Compile with clm -h 1500m -s 50m -fusion -t -IL Dynamics -IL StdEnv -IL Platform main.

You can get the version TIO (and myself) use from the link in the heading, or a more recent one from here.

• I don't think this code gives the right output. I tried it with s=8 and it gives [9,86,126,130,130,130,130,130,130] – Anush Nov 6 '18 at 20:44
• @Anush hmm I know I tested it. I'll see if I changed anything between that and the posted one, give me a few hours and I can do it on my break. – Οurous Nov 6 '18 at 21:27
• @Anush Why are you providing s`? In the question you state "For a given n, your code should output the answer for all values of s from 1 to 9." – Οurous Nov 6 '18 at 23:51
• I think that is what you call a brain freeze on my part :) I will time your code now. – Anush Nov 7 '18 at 8:59