Ordered partitions: Difference between revisions

Line 1,974:

=={{header|Phix}}==

Uses the permutes() routine [new in 1.0.2], which handles duplicate elements properly, so in the {1,2,3,4} test

Note that the builtin permute() function returns results in an idiosyncratic manner, so we use sort a lot and check for duplicates,

this only generates 12,600 combinations, whereas the previous version generated and obviously filtered and sorted

which might make this a tad inefficient.

all of the possible 3,628,800 full permutations, therefore it is now at least a couple of hundred times faster.

<lang Phix>function partitions(sequence s)

integer N = sum(s)

with javascript_semantics

sequence set = tagset(N), perm,

requires("1.0.2")

results = {}, result, resi

function partitions(sequence s)

for i=1 to factorial(N) do

integer l = length(s), N = sum(s)

perm = permute(i,set)

sequence pset = {}, -- eg s==={2,0,2} -> {1,1,3,3}

integer n = 1

rn = repeat(0,l) -- "" -> <nowiki>{{</nowiki>0,0},{},{0,0<nowiki>}}</nowiki>

result = {}

for i=1 to l do

for j=1 to length(s) do

pset &= repeat(i,s[i])

resi = {}

rn[i] = repeat(0,s[i])

for k=1 to s[j] do

end for

resi = append(resi,perm[n])

if pset={} then return {rn} end if -- edge case

n += 1

sequence res = permutes(pset,0)

end for

-- eg {1,1,3,3} means put 1,2 in [1], 3,4 in [3]

result = append(result,sort(resi))

-- .. {3,3,1,1} means put 1,2 in [3], 3,4 in [1]

end for

for i=1 to length(res) do

if not find(result,results) then

sequence ri = res[i], -- a "flat" permute

results = append(results,result)

rdii = repeat(1,l) -- where per set

end if

integer rii = 0

end for

for j=1 to length(ri) do

return sort(results)

integer rdx = ri[j], -- which set

end function

rnx = rdii[rdx] -- wherein""

rii += 1

ppOpt({pp_Nest,1})

rn[rdx][rnx] = rii -- plant 1..N

pp(partitions({2,0,2}))

rdii[rdx] = rnx+1

pp(partitions({1,1,1}))

end for

pp(partitions({1,2,0,1}))

assert(rii=N)

pp(partitions({}))

res[i] = deep_copy(rn)

pp(partitions({0,0,0}))</lang>

end for

return res

end function

procedure test(sequence p)

sequence q = partitions(p)

string {ia,s} = iff(length(q)=1?{"is",""}:{"are","s"})

printf(1,"There %s %,d ordered partion%s for %v:\n{%s}\n",

{ia,length(q),s,p,join(shorten(q,"",5,"%v"),"\n ")})

end procedure

papply({{2,0,2},{1,1,1},{1,2,0,1},{1,2,3,4},{},{0,0,0}},test)

<pre>

There are 6 ordered partions for {2,0,2}:

⚫

{{{~~1,2~~}, {}, {~~3,4~~}},

{{1,3}, {}, {2,4}},

{{{1,2},{},{3,4}}

{{1,4}, {}, {2,3}},

{{1,3},{},{2,4}}

{{2,3}, {}, {1,4}},

{{1,4},{},{2,3}}

{{2,4}, {}, {1,3}},

{{2,3},{},{1,4}}

{{3,4}, {}, {1,2}}}

{{2,4},{},{1,3}}

{{{1}, {2}, {3}},

{{3,4},{},{1,2}}}

There are 6 ordered partions for {1,1,1}:

⚫

{{1}, {3}, {2}},

{{2}, {1}, {3}},

{{{1},{2},{3}}

{{2}, {3}, {1}},

{{1},{3},{2}}

{{3}, {1}, {2}},

{{2},{1},{3}}

{{3}, {2}, {1}}}

{{3},{1},{2}}

{{{1}, {2,3}, {}~~, {4~~}},

{{2},{3},{1}}

{{1}, {2,4}, {}~~, {3~~}},

{{3},{2},{1}}}

There are 12 ordered partions for {1,2,0,1}:

⚫

{{1}, {3,4}, {}, {2}},

{{2}, {1,3}, {}, {4}},

{{{1},{2,3},{},{4}}

{{2}, {1,4}, {}, {3}},

{{1},{2,4},{},{3}}

{{2}, {3,4}, {}, {1}},

{{1},{3,4},{},{2}}

{{3}, {1,2}, {}, {4}},

{{2},{1,3},{},{4}}

{{3}, {1,4}, {}, {2}},

{{2},{1,4},{},{3}}

{{3}, {2,4}, {}, {1}},

{{3},{1,2},{},{4}}

{{4}, {1,2}, {}, {3}},

{{4},{1,2},{},{3}}

{{4}, {1,3}, {}, {2}},

{{3},{1,4},{},{2}}

{{4}, {2,3}, {}, {1}}}

{{4},{1,3},{},{2}}

⚫

{{2},{3,4},{},{1}}

⚫

{{3},{2,4},{},{1}}

⚫

{{4},{2,3},{},{1}}}

There are 12,600 ordered partions for {1,2,3,4}:

{{{1},{2,3},{4,5,6},{7,8,9,10}}

{{1},{2,3},{4,5,7},{6,8,9,10}}

{{1},{2,3},{4,5,8},{6,7,9,10}}

{{1},{2,3},{4,5,9},{6,7,8,10}}

{{1},{2,3},{4,5,10},{6,7,8,9}}

...

{{9},{7,10},{5,6,8},{1,2,3,4}}

{{10},{7,9},{5,6,8},{1,2,3,4}}

{{8},{9,10},{5,6,7},{1,2,3,4}}

{{9},{8,10},{5,6,7},{1,2,3,4}}

{{10},{8,9},{5,6,7},{1,2,3,4}}}

There is 1 ordered partion for {}:

{{}}

There is 1 ordered partion for {0,0,0}:

⚫

{{{}, {}, {}}}

⚫

{{{},{},{}}}

</pre>