#Cartesian Product

1 messages · Page 1 of 1 (latest)

last star
#

Feeling a little dim, but what would be the best way to implement a function that gets the cartesian product of []T with n repeats so something with a signature of comptime T: type, allocator: std.mem.Allocator, items: []T, repeat: usize) ![][]T where the output is a slice that is items.len * n and contains slices of len n.

If it was just a one off and i did not need to support a dynamic value of n i would just write it as nested loops, and preallocate everything.

merry cedar
#

you can allocate the big slice (the [][]T one), than populate it in a loop with slices acquired via std.mem.Allocator.dupe. an errdefer is required to free all of the allocated slices in case of an allocation failure.
I would suggest you take a step back and evaluate whether you need such function in the first place, and whether there might be better ways to represent your data, as compared to this slice-of-slices

last star
#

well i could likely implement as a iterator as well, but yeah what i am struggling with is more basic, which is how to transform something like this

fn product2(comptime T: type, allocator: std.mem.Allocator, items: []const T) ![][2]T {
    var result = try allocator.alloc([2]T, items.len * 2);
    errdefer allocator.free(result);

    var index: usize = 0;

    for (items) |y| {
        for (items) |x| {
            result[index] = .{x, y};
            index += 1;
        }
    }

    return result;
}

to one where i can just pass in n which is anything above 0 instead of it being hardcoded to 2 loops

merry cedar
last star
#

yeah exactly

merry cedar
#

that's a bit spicier... recursion might be in order

crystal obsidian
#

currently working out how to do it without recursion as a fun puzzle (thanks!) but for one thing: in your example is the result's length not pow(items.len, 2) not items.len * 2

merry cedar
#

...as @crystal obsidian wrote before me :)

last star
crystal obsidian
#

ok I've got it I think, just writing up an algo in pseudocode give me a min

last star
#

yeah i feel a bit dim not knowing this, but last time i have had to do this was in python where i can be lazy since it has a bunch of functions for this stuff in itertools

merry cedar
last star
#

oh i was not expecting it too

#

also there is not really a good way to describe this in zig that would give enough control in all situations

#

so makes sense to leave that up to the user to implement

crystal obsidian
# 
num_output = pow(items.len, n)
res = alloc(num_output n-length-slices)
for i in [0, num_output)
  tmp = i
  for j in [0, n)
    res[i][j] = items[items.len - (tmp % n) - 1]
    tmp /= n
#

idea is to treat each representation as a sequence of digits n long in base items.length

merry cedar
#

(if we want the result be lexically ordered)

crystal obsidian
#

yeah that'd be nicer

#

editing

last star
#

thanks will give it a try

merry cedar
#

here's my (untested) translation of @crystal obsidian's algorithm into Zig:
||```rs
pub fn nthCartesian(comptime T: type, set: []const T, n: usize, allocator: std.mem.Allocator) [][]T {
// allocate all memory before population...
const container = try allocator.alloc([]T, std.math.pow(usize, set.len, n));
for (container, 0..) |item, i| {
errdefer {
for (container[0..i]) |del| allocator.free(del);
allocator.free(container);
}
item. = try allocator.alloc(T, n);
}

for (container, 0..) |item, i| {
    var tmp = i;
    var it = std.mem.reverseIterator(item);
    while (it.nextPtr()) |el| {
        el.* = set[tmp % set.len];
        tmp /= set.len;
    }
}
return container;

}

last star
#

cool thanks will give it a try, and get back to you. also can i ask a convention question since i am still very new to zig. i thought generally allocator was supposed to be the first non comptime arg

merry cedar
last star
#

yeah guess language is still young

#

am used to there being some convention around that since one of my most used languages lately is Go, and there is defiantly a bunch of convention around some of the dependencies that are pretty passed to everything like context

crystal obsidian
#

just had a try and looks like your implementation works @merry cedar

merry cedar
#

nice!

crystal obsidian
#

would be nice if we could a single allocation though, given we know the exact size of the result

merry cedar
#

that's true: we can allocate a single []T slice of length std.math.pow(set.len, n) * n and use that - I adhered to the original requirements, but I'd definitely suggest using a single-slice approach instead

crystal obsidian
#

it's a bit annoying that allocator.alloc([n]T, product_count) doesn't work. I know when you declare an array on the stack you need the length but surely the compiler could trivially work out the size of [n]T

#

i.e. n * sizeof(T) + slice_overhead

merry cedar
last star
crystal obsidian
#

yeah you're right, that's not the intent of what I want

#

just got to be a nicer way of allocating 2D+ structures

#

The fragmentation and multiple calls to allocate cost just seems silly, where in c I'd just malloc the whole thing in one go

last star
#

well could just avoid the issue in some cases

#

like normally if its a 2d+ structure for say a grid or something for a game or like a image i just use a 1d array and do the math to convert x and y to a index

#

only works if you know the width up front and its not jagged of course

#

actually about a nicer way, in zig since allocators are oftne passed around is it common for people to just wrap it in a different allocator