How to generate all possible combinations of numbers with grouping

Question

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!

Answer 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!

Answer 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.

Answer 3

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.

Answer 4

Thanks, that’s really awesome. I’ll have to take my time to reverse-engineer it but already see it’s very neat!

Answer 5

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.

Answer 6

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

Answer 7

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].

Answer 8

Thanks! Yes, it’s being quite fun... 😉