Make every fixed list

Question

We are to define the idea of a fixed list as follows:

• A fixed list is a list of fixed lists.

This definition is recursive so it's useful to look at some examples.

• The empty list [] is a fixed list.
• And list of empty lists is a fixed list. e.g. [[],[],[]]
• Any list of the above two is also a fixed list. e.g. [[],[],[[],[],[]]]

We can also think of these as "ragged lists" with no elements, just more lists.

Task

In this challenge you will implement a function \$g\$ which takes as input an fixed list and as output produces a fixed list.

The only requirement is that there must be some fixed list \$e\$, such that you can produce every fixed list eventually by just applying \$g\$ enough times.

For those more inclined to formulae, here's that expressed as symbols:

\$ \exists e : \mathrm{Fixt}, \forall x : \mathrm{Fixt} , \exists n : \mathbb{N}, g^n(e) = x \$

You can implement any function you wish as long as it meets this requirement.

This is code-golf so answers will be scored in bytes with fewer bytes being the goal

Answer 1

Python 2,  168  164 bytes

-3 thanks to pxeger! (In-place list addtion r=...;r+=[] to r=...+[] >.<)

^{No doubt there is a far terser way, but this is quite a fun way...}

j=''.join
n=int(j(`ord(c)%3`for c in`input()`if','<c),2)
while 1:
 try:n+=1;r=eval(j('[]'[i<'1']for i in bin(n)[2:]).replace('][','],['))+[]
 except:1
 else:exit(r)

A full program that accepts a fixed list as input and prints the next fixed list in an order defined by a binary encoding where [ is a 1 and ] is a 0 (ignoring and ,). The integer sequence of this ordering is listed on the OEIS under A057547.

Try it online! ...or see this slightly augmented code to see the the ordering.

How?

First the input list is encoded as a binary number by reading left to right and treating encountered [ as 1s and ] as 0s.
Then this number is incremented and we form the decoded pattern of [ and ] , place , between any ][ and try to evaluate this as Python code.
If this evaluates as a list* we exit and print that list representation to STDERR. If not, we increment our number and try again.

* There are also strings we form that are valid tuples, rather than lists, like "[],[]" -> ([], []) which we must ignore. This is handled by attempting to concatenate an empty list to the end inside the try block, which fails for tuples, and is a no-op for lists.

Answer 2

Python, 170 bytes

d=lambda X:(1-(","in str(X)))*len(str(X))//2
e=[[]]
def f(X):L,*R=X or e;return X and(d(R)and(d(L)and(R and[d(L)*e]+(d(R)-2)*e or d(X)*e)or[f(L)]+~-d(R)*e)or[L]+f(R))or e

Attempt This Online!

Old Python, 200 bytes

d=lambda X:1+max([*map(d,X),-1])
s=lambda X:1+sum(map(s,X))
e=[[]]
def f(X):L,*R=X or e;return X and(~d(R)==-s(R)and(~d(L)==-s(L)and(R and[-~d(L)*e]+~-d(R)*e or-~d(X)*e)or[f(L)]+d(R)*e)or[L]+f(R))or e

Attempt This Online!

This enumerates based on an order which sorts first by number of nodes and then by "breadth-over-depth", i.e. for example [[],[],[]] < [[[[]]]]. These are the first and last with 3 nodes (plus root). How does it look in between? We split into first element and of root list and root list minus first element and order first by number of nodes within either; the example has 0,2 ([[],[],[]] -> [], [[],[]]) and 2,0 ([[[[]]]] -> [[[]]], []). Whatever conceptual gaps may be still there are resolved recursively, with lexicographic order at each split.

The implementation has to find the direct successor of its input. This is done using the same recursive splitting. To manage the "carry" in the lexicographic and outermost orderings we use helper functions d (depth) which returns the height of subtree under investigation but only if it is a pure tower and therefore has no successor, triggering carry to the next more significant subtree. Carry simply means the triggering subtree is reset to a flat list and the triggered subtree is incremented if possible. If not, the number of nodes is incrermented and the entire tree reset to flat.

Answer 3

JavaScript (Node.js), 102 bytes

I=([h,...t])=>h?h[0]?[D(h),...I(t)]:[I(t)]:[[]]
D=([h,...t])=>t[0]?[I(h),...D(t)]:h[0]?[[],...D(h)]:[]

Try it online!

I calculate succ, while D calculate prev. I hope it corrects...

---

JavaScript (SpiderMonkey), 94 bytes

I=([h,...t])=>h?h[0]?[D(h),...I(t)]:[I(t)]:[[]]
D=(a,b=[],U=uneval)=>U(I(b))==U(a)?b:D(a,I(b))

Try it online!

Answer 4

JavaScript (ES6), 134 bytes

Expects and returns a string.

f=(S,i=0)=>(F=(n=i++,o=r=[],s=[])=>n?n%2?F(n>>1,q=[],[...s,o],o.push(q)):s[0]?F(n>>1,s.pop(),s):F():JSON.stringify(r))()==S?F():f(S,i)

Try it online!

Answer 5

Retina 0.8.2, 54 bytes

,

(^|]\[)(\[)*(?<4-2>])*(]*)$
[$3$#4$*1]
1
[]
]\[
],[

Try it online! Link includes test cases. Directly calculates the next string of equal numbers of [s and ]s that satisfy the conditions that every prefix contains more [s than ]s, ordered by length and then lexicographically. Explanation:

,

Remove all commas from the input.

(^|]\[)(\[)*(?<4-2>])*(]*)$

Match a run of [s followed by a run of ]s at the end of the string. Capture starting either at the beginning of the string (for an input of that form) or just after a ][ pair. Subtract the count of [s from the count of ]s. (This is done by matching a ] for every [ using a .NET balancing group, and then matching the leftover ]s at the end.)

[$3$#4$*1]

Insert the leftover ]s followed by a [] pair (marked with a 1 for now) for each [, the whole thing being wrapped in [ and ], which make up for the ][ pair matched at the start, but also serve to extend the string if it was of the form [ followed by ]s.

1
[]

Expand the 1s into []s. (This can be written more succinctly in Retina 1 using [$3$#4*$([])].)

]\[
],[

Restore all necessary commas.

Answer 6

Ruby, 156 bytes

f=->l,x=1,q=p{r=0;w=x.digits(2).map{|d|r+=d+d-1};w.pop==0&&w.max<0&&(k=eval x.digits(2).map{|x|"]["[x]}.reverse.join.gsub("][","],[");q)?k:f[l,x+1,q||l==k]}

Try it online!

Work in progress.

Answer 7

Charcoal, 57 bytes

≔⁻Ｓ,θ≔…⮌θ⌕⮌⁺][θ[]η⪫⪪⪫⟦…θ⁻⁻ＬθＬη²[×]⁻№η]№η[×[]№η[¦]⟧ω][¦],[

Try it online! Link is to verbose version of code. Note that Charcoal's default input auto-converts a fixed list from JSON input format, so you actually have to wrap the string in JSON for Charcoal to read it as a string. Explanation: Port of my Retina 0.8.2 answer.

≔⁻Ｓ,θ

Remove commas from the input.

≔…⮌θ⌕⮌⁺][θ[]η

Get the suffix of the string after the last ][ (or the whole string if there is no ][).

⪫⪪⪫⟦…θ⁻⁻ＬθＬη²[×]⁻№η]№η[×[]№η[¦]⟧ω][¦],[

Concatenate the prefix of the string, a [, ]s to make up the difference in numbers of [s and ]s in the suffix, []s for each [ in the suffix, and a final ], then reinsert commas as necessary.

Answer 8

05AB1E, 20 bytes

¯[Dæ«DÙDÅΔIQ}>èDgĀ#\

Try it online!

All values

Uses the fact that the infinite list defined by repeatedly applying x += powerset(x) (+ is list concatenation) contains all fixed lists (it's easily proven with induction). It repeatedly does that, starting from the empty set, and each time looks at the element following the input in the current list uniquified. If the input isn't in the array it will look at the -1 + 1 element which is an empty set so it will continue. If the input is the last element due to modular indexing it'll also look at the first element and continue. Otherwise, there is a next element, and it will output it.