Return to Answer

replaced http://mathematica.stackexchange.com/ with https://mathematica.stackexchange.com/

Source Link

edited Apr 13, 2017 at 12:55

Parentheses are a grouping operation. So, instead of using higher precedence operators, there is the potential for a lot of savings if we determine the non-overlapping partitions non-overlapping partitions, first. Applying Mr. Wizard's code to the problem of combining $123$, for instance

At this point, there are two approaches that come to mind to save memory, and this is where my solution becomes a bit fuzzy. First, only work with specific lengths of the operator tuples at a time. Since the pieces have specific lengths, it makes sense only to work worth those tuples that we need at any specific point. The same technique can be applied to incorporating the parenthesized pieces into the larger lists as a second loop. For the second pass, the operator tuples could have been serialized to disk, first, so you do not have to recalculate them. Second, as each length of operator tuples contains the prior lengths as substrings, I would suggest using a prefix tree prefix tree, or trie, to minimize the storage requirements. This method still requires at least two passes, though.

Parentheses are a grouping operation. So, instead of using higher precedence operators, there is the potential for a lot of savings if we determine the non-overlapping partitions, first. Applying Mr. Wizard's code to the problem of combining $123$, for instance

At this point, there are two approaches that come to mind to save memory, and this is where my solution becomes a bit fuzzy. First, only work with specific lengths of the operator tuples at a time. Since the pieces have specific lengths, it makes sense only to work worth those tuples that we need at any specific point. The same technique can be applied to incorporating the parenthesized pieces into the larger lists as a second loop. For the second pass, the operator tuples could have been serialized to disk, first, so you do not have to recalculate them. Second, as each length of operator tuples contains the prior lengths as substrings, I would suggest using a prefix tree, or trie, to minimize the storage requirements. This method still requires at least two passes, though.

Parentheses are a grouping operation. So, instead of using higher precedence operators, there is the potential for a lot of savings if we determine the non-overlapping partitions, first. Applying Mr. Wizard's code to the problem of combining $123$, for instance

At this point, there are two approaches that come to mind to save memory, and this is where my solution becomes a bit fuzzy. First, only work with specific lengths of the operator tuples at a time. Since the pieces have specific lengths, it makes sense only to work worth those tuples that we need at any specific point. The same technique can be applied to incorporating the parenthesized pieces into the larger lists as a second loop. For the second pass, the operator tuples could have been serialized to disk, first, so you do not have to recalculate them. Second, as each length of operator tuples contains the prior lengths as substrings, I would suggest using a prefix tree, or trie, to minimize the storage requirements. This method still requires at least two passes, though.

Source Link

created Nov 23, 2012 at 15:47

rcollyer

34.1k
7
94
194

I am a bit late to the party, and with an incomplete answer. I will flesh this out if I find the time, but that is not likely for a little while.

Parentheses are a grouping operation. So, instead of using higher precedence operators, there is the potential for a lot of savings if we determine the non-overlapping partitions, first. Applying Mr. Wizard's code to the problem of combining $123$, for instance

data = Range[3];

parts = Join @@ Permutations /@ IntegerPartitions[Length@data];
results = (Internal`PartitionRagged[data, #] & /@ parts)
(* {{{1, 2, 3}}, {{1, 2}, {3}}, {{1}, {2, 3}}, {{1}, {2}, {3}}} *)

leaves us with 4 ways of uniquely grouping the numbers. This rises to 256 with data = Range[9]. But, the groupings {1}, {2}, etc. are redundant, however removing those will only reduce it to 3 (255) ways to group them. Instead, we want to reorganize our data to make use of the groupings, so

pieces = 
 MapIndexed[
   # -> a[#2[[1]]] &, 
   Union[Flatten[(Internal`PartitionRagged[data, #] & /@ parts), 1]
 ] /. a_List /; Length[a] == 1 :> Sequence[]]
(*{{1, 2} -> a[1], {2, 3} -> a[2], {1, 2, 3} -> a[3]}*)

which is 36 elements long with data = Range[9], and applying it to results

reduced = results /. List[b_]:> b /. pieces
(* {a[3], {1, a[2]}, {a[1], 3}} *)

This means we have

Length@pieces + Length@Select[reduced, Head[#] =!= a &]
(* 5, or 290 *)

sequences to work with.

At this point, there are two approaches that come to mind to save memory, and this is where my solution becomes a bit fuzzy. First, only work with specific lengths of the operator tuples at a time. Since the pieces have specific lengths, it makes sense only to work worth those tuples that we need at any specific point. The same technique can be applied to incorporating the parenthesized pieces into the larger lists as a second loop. For the second pass, the operator tuples could have been serialized to disk, first, so you do not have to recalculate them. Second, as each length of operator tuples contains the prior lengths as substrings, I would suggest using a prefix tree, or trie, to minimize the storage requirements. This method still requires at least two passes, though.

There are two concerns I have that I have not had time to address, hence the incompleteness of this answer. First, I have not said anything about concatenation. It, too, can be viewed as a grouping operation, and as it as the highest precedence, it could be implemented as a first pass. Obviously, this makes it a little messier, but that is what you get when engineering around constraints. Second, I have not yet addressed how to associate a particular operator tuple sequence with its result. Until I do, this method can be used to calculate the number of combinations, but that is about it.