0

I am trying to write a function which generates all unique combinations of arrays for values up to a certain number.

The function has two parameters, one parameter is the length of the array and the other is the maximum size of the integer.

F(4, 3) is a function that will generate all possible unique combinations of positive integers less than or equal to 4 in a three integer array. F(10, 100) will generate all possible unique combinations of positive integers less than or equal to 10 in a 100 integer array.

The result for F(4, 3) would start like this:

(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 1), (1, 2, 2) ... (4, 4, 4)

F(10, 10) would start like this:

(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1, 1, 1, 1, 2), ... (10, 10, 10, 10, 10, 10, 10, 10, 10, 10)

funcylambda
  • 19
  • 1
  • 3
  • You second example does not look correct, since `i` and `j` are always the same. Furthermore it is not clear to me what to do in case the limit is less than the number of elements: which elements should be generated in that case? The smallest lexicographically? – Willem Van Onsem Sep 27 '18 at 20:14
  • 5
    Are you *sure* "Cartesian product" is the right term for what you want? I can't match my understanding of "Cartesian product" with your input/output examples. (I also can't understand the logic behind your input/output examples.) – Daniel Wagner Sep 27 '18 at 20:18
  • In your second example the tuples are still size 2, not 100. – karakfa Sep 27 '18 at 20:23
  • Why are the values wrapped in a 2-tuple? If the length depends on a parameter, normally this should be a list. – Willem Van Onsem Sep 27 '18 at 20:27
  • What do you mean "by fixed array size of 2"? – Code-Apprentice Sep 27 '18 at 20:33
  • 3
    `f x y = replicateM y [1 .. x]` – melpomene Sep 27 '18 at 20:58
  • I wrote the question while still thinking about it and therefore made a load of mistakes, I've now re-written the question and believe it is all there. – funcylambda Sep 27 '18 at 20:58
  • Thanks for the improved example – Code-Apprentice Sep 27 '18 at 20:59
  • Can you clarify your meaning of "array"? Your example is a three integer tuple, but you called it an array? Just wonderin' cuz tuples, arrays, and lists have very different meanings in Haskell. i.e. `[i,j,k]` is not the same as `(i,j,k)` – dopamane Sep 27 '18 at 21:03
  • 1
    @DavOS - I don't think it really matters which one is used, but I meant array with my C# hat on - a list, a collection, something I can later iterate over and that's it. Can you think of a reason this might matter? I'd be interested to know! – funcylambda Sep 27 '18 at 21:32
  • 2
    StackOverflow is not a service to get people to write your code - it's a way to ask for help with a specific problem. Can you provide an example of what you've already tried, and why it isn't working? – Isaac van Bakel Sep 27 '18 at 23:55
  • @IsaacvanBakel - I originally provided my attempt of a solution by framing the question from where I was but found this led to too much confusion (there were almost 15 more comments than what you're seeing now). – funcylambda Sep 28 '18 at 07:04

1 Answers1

0

There are P=Max**Len arrays for F(Max, Len), and there is bijection between numbers in range 0..P-1 and arrays.

So you can just walk in the loop through all numbers in that range and represent loop counter in M-ric numeral system (counter 4(dec) corresponds to (1, 2, 1) in your first example)

Alternate way - use array as multidigit counter (like old electrical meter display with rotating cylinders). When some digit becomes Max and should be incremented, it is reset to 1 and the next digit is incremented ((1, 1, 4) => (1, 2, 1) in your example).

MBo
  • 77,366
  • 5
  • 53
  • 86