How to use zig to implement permutations funcs writen in golang?

Help
1

Golang code:

package main

import "fmt"

func Combine(arr []int, k int) [][]int {
	var res [][]int
	dfs(arr, k, 0, []int{}, &res)
	return res
}

func dfs(graph []int, target int, index int, path []int, paths *[][]int) {
	if len(path) == target {
		tmp := make([]int, target)
		copy(tmp, path)
		*paths = append(*paths, tmp)
		return
	}
	for i, v := range graph {
		// fmt.Println("*************: ", i, v)
		if i < index {
			// fmt.Printf("-----%d\t%d\n", i, index)
			continue
		}
		dfs(graph, target, index+1, append(path, v), paths)
		index++
	}
}

func Permute(arr []int) [][]int {
	var res [][]int
	toNext(arr, 0, &res)
	return res
}

func toNext(arr []int, n int, res *[][]int) {
	if n == len(arr)-1 {
		tmp := make([]int, len(arr))
		copy(tmp, arr)
		*res = append(*res, tmp)
	}
	for i := n; i < len(arr); i++ {
		arr[i], arr[n] = arr[n], arr[i]
		toNext(arr, n+1, res)
		arr[i], arr[n] = arr[n], arr[i]
	}
}

func Permutations(arr []int, k int) [][]int {
	var res [][]int
	_res := Combine(arr, k)
	fmt.Println("_res: ", _res)
	for _, v := range _res {
		res = append(res, Permute(v)...)
	}
	return res
}

func main() {
	arr := []int{3, 4, 6, 10, 15, 17}
	ret := Permutations(arr, 2)
	fmt.Println(len(ret))
	fmt.Println(ret)
}

My zig code:

const std = @import("std");

const allocator = std.heap.page_allocator;

pub fn Combine(arr: []isize, k: isize) ![][]isize {
    var ret = std.ArrayList([]isize).init(allocator);
    defer ret.deinit();

    var path = std.ArrayList(isize).init(allocator);
    defer path.deinit();

    try dfs(arr, k, 0, &path, &ret);
    // var index: isize = 0;
    // try dfs(arr, k, &index, &path, &ret);

    return ret.toOwnedSlice();
}

fn dfs(graph: []isize, target: isize, index: isize, path: *std.ArrayList(isize), paths: *std.ArrayList([]isize)) !void {
    // fn dfs(graph: []isize, target: isize, index: *isize, path: *std.ArrayList(isize), paths: *std.ArrayList([]isize)) !void {
    if (path.items.len == target) {
        var tmp = try allocator.alloc(isize, @intCast(usize, target));
        std.mem.copy(isize, tmp, path.toOwnedSlice());
        try paths.append(tmp);
        return;
    }
    var idx: isize = index;
    for (graph) |v, i| {
        // std.debug.print("**********: {}\t{}\n", .{ i, v });
        if (i < idx) {
            // std.debug.print("-----{}\t{}\n", .{ i, idx });
            continue;
        }
        // if (i < index.*) {
        //     std.debug.print("----{}\t{}\n", .{ i, index.* });
        //     continue;
        // }
        try path.append(v);
        try dfs(graph, target, idx + 1, path, paths);
        idx += 1;
        // var idx = index.* + 1;
        // try dfs(graph, target, &idx, path, paths);
        // index.* += 1;
    }
}

pub fn Permute(arr: []isize) ![][]isize {
    var ret = std.ArrayList([]isize).init(allocator);
    defer ret.deinit();

    try toNext(arr, 0, &ret);

    return ret.toOwnedSlice();
}

fn toNext(arr: []isize, n: isize, ret: *std.ArrayList([]isize)) !void {
    if (n == arr.len - 1) {
        var tmp = try allocator.alloc(isize, arr.len);
        std.mem.copy(isize, tmp, arr);
        try ret.append(tmp);
    }
    var i: usize = @intCast(usize, n);
    while (i < arr.len) : (i += 1) {
        std.mem.swap(isize, &arr[i], &arr[@intCast(usize, n)]);
        try toNext(arr, n + 1, ret);
        std.mem.swap(isize, &arr[i], &arr[@intCast(usize, n)]);
    }
}

pub fn Permutations(arr: []isize, k: isize) ![][]isize {
    var ret = std.ArrayList([]isize).init(allocator);
    defer ret.deinit();

    const _ret = try Combine(arr, k);
    std.debug.print("_ret: {any}\n", .{_ret});
    for (_ret) |v| {
        try ret.appendSlice(try Permute(v));
    }

    return ret.toOwnedSlice();
}

pub fn main() !void {
    var arr = [_]isize{ 3, 4, 6, 10, 15, 17 };
    var ret = try Permutations(&arr, 2);
    std.debug.print("main: {}\n", .{ret.len});
    std.debug.print("main: {any}\n", .{ret});
}

Golang result:

_res:  [[3 4] [3 6] [3 10] [3 15] [3 17] [4 6] [4 10] [4 15] [4 17] [6 10] [6 15] [6 17] [10 15] [10 17] [15 17]]
30
[[3 4] [4 3] [3 6] [6 3] [3 10] [10 3] [3 15] [15 3] [3 17] [17 3] [4 6] [6 4] [4 10] [10 4] [4 15] [15 4] [4 17] [17 4] [6 10] [10 6] [6 15] [15 6] [6 17] [17 6] [10 15] [15 10] [10 17] [17 10] [15 17] [17 15]]

My zig result:

_ret: { { 3, 4 }, { 6, 10 }, { 15, 17 }, { 17, 10 }, { 15, 17 }, { 17, 4 }, { 6, 10 }, { 15, 17 }, { 17, 10 }, { 15, 17 } }
main: 20
main: { { 3, 4 }, { 4, 3 }, { 6, 10 }, { 10, 6 }, { 15, 17 }, { 17, 15 }, { 17, 10 }, { 10, 17 }, { 15, 17 }, { 17, 15 }, { 17, 4 }, { 4, 17 }, { 6, 10 }, { 10, 6 }, { 15, 17 }, { 17, 15 }, { 17, 10 }, { 10, 17 }, { 15, 17 }, { 17, 15 } }

Who can tell me where my code is wrong? Thank you very much.

2

Just a guess… not sure this is the real reason.
append can reallocate, so pointers to individual items of a list may become wrong.

To illustrate, run this code:

const std = @import("std");
const Allocator = std.mem.Allocator;
const MyList = std.ArrayList(usize);

pub fn main() !void {

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    var list = MyList.init(allocator);

    var k: usize = 0;
    while (k < 16) {
        try list.append(k);
        std.debug.print("{}\n", .{&list.items[0]});
        k += 1;
    }
}

$ ./al
usize@7f0bf8812000
usize@7f0bf8812000
usize@7f0bf8812000
usize@7f0bf8812000
usize@7f0bf8812000
usize@7f0bf8812000
usize@7f0bf8812000
usize@7f0bf8812000
usize@7f0bf8815000  <<< reallocation occured
....

(Initially ArrayList has capacity of 8 items)

1 Like
3

Thank you very much.
I have used Combinations function instead of Combine function and dfs function.