+ 2

How to generate all possible combinations of numbers with grouping

Hi, just trying to smash through the Friedman challenge and I have probably figured out most of it but I am not sure how to generate the number combinations that I need. These aren't the good ol' combinations because apart from the order, you can group the digits. eg. [6, 7, 4, 5] means not only [4, 5, 7, 6] but can be also: [45, 7, 6] or even [674, 5] and [67,45]. Essentially, any set of numbers without repetitions. If there's anything language specific, I am (trying to become) a Rubyist. Excuse the non-scientific wording. Let know your ideas. Many thanks y'all!

4th Aug 2018, 9:32 PM
luke.pchr
luke.pchr - avatar
8 odpowiedzi
+ 1
You're welcome! By looking at the output you can get a feel for how the algorithm is building up the list: https://i.imgur.com/ZRpEGrG.png The orange part growing is the inner `offset2` variable increasing, the blue part is the outer `offset`; the right part does the same but on a smaller scale. Anyway happy hacking!
4th Aug 2018, 11:30 PM
Schindlabua
Schindlabua - avatar
+ 2
You probably have some code to handle the individual operations like + - etc, right? You can think of "grouping" as just another operator: group(a, b) = a * 10 + b, that gives you a number with the digits put next to each other. Only thing to keep in mind is that `b` needs to be single-digit, `a` can be any length. So you can just use the usual ways to generate permutations without bothering about grouping the digits.
4th Aug 2018, 9:46 PM
Schindlabua
Schindlabua - avatar
+ 2
You are right, it turned out to be pretty tough! https://code.sololearn.com/WV2rUHVFvYmM/?ref=app Basically what I did is split the list in 3: the first third part I left alone, the second part I grouped into a number, and on the third part I used recursion to generate all possible subgroups. For example [1,2,3,4,5,6] turns to [1,2 | 34 | 5,6] By splitting the list at each possible location I can generate all possible partitions. The hard part was not generating things twice but I eventually got it :) I can explain in more detail if you want.
4th Aug 2018, 11:10 PM
Schindlabua
Schindlabua - avatar
+ 1
Thanks, that’s really awesome. I’ll have to take my time to reverse-engineer it but already see it’s very neat!
4th Aug 2018, 11:22 PM
luke.pchr
luke.pchr - avatar
+ 1
Hiya! Could you explain a bit more about what happens in the line 23 - "the JS stuff to combine everything"? I know that we have an array, integer and array again but the way everything is put together has turned out to be a bit tricky to figure out. How is an arrow-less representation of this looking? There are some differences between JS and Ruby in terms of what parameters are required but more or less there are the same methods. I committed many Ruby codes that produce wrong results like this below but I start to realise I have pretty much no idea what I'm doing! I mean, they do run... ;) ps = ps.concat(back.map.with_index{|item,index| ps[index] + front[index] + number.to_s + back[index]} ) At least now I know they are not the same indexes in different arrays. I was close to dropping the thing but decided to understand instead.
19th Aug 2018, 7:20 PM
luke.pchr
luke.pchr - avatar
+ 1
Still working at the problem huh, nice! It's probably best explained with an example: If you look at the image I posted right where the blue comes in, we have front: [1] number: 23 back: [ [4,5,6], [45,6], [456] [4,56] ] In other words we subdivide the problem and the `back` array gets all partitions for the list [4,5,6]. To make a "full" partition out of that we have to prepend `front` and `number` to each partition in `back`. So we'd end up with [ [1,23,4,5,6], [1,23,45,6], [1,23,456], [1,23,4,56] ] Then you take that list and add it to your output list (that's the .concat). So in pseudocode it's something like for(sub_partition of back) output_array += front + [number] + sub_partition; Hope that helps! If that is the first recursive function you're working with, you've picked a tricky one :P
19th Aug 2018, 7:41 PM
Schindlabua
Schindlabua - avatar
0
This sounds good, but what would happen if the input was larger than 1000 though? Both 2 and 3-digits numbers would be allowed and as far as I understand, two 2-digit numbers should be also taken into consideration? The [ab, cd].
4th Aug 2018, 10:03 PM
luke.pchr
luke.pchr - avatar
0
Thanks! Yes, it’s being quite fun... 😉
20th Aug 2018, 8:07 AM
luke.pchr
luke.pchr - avatar