使用倍数索引的Swift算法枚举多线性映射：[Int] [英] Swift algorithm to enumerate a multilinear map, using multiples indexes:[Int]

问题描述

多线性映射M的元素存储在长度为N的一维数组中，形状S由 S定义：[Int] = [p，q，r，...] ，这样 q * p * r * ... = N 。 Shape的大小可变，在编译时不知道。

A multilinear map M has its elements stored in a one-dimension array of length N, with a Shape S defined by S:[Int] = [p,q,r,...] so that q*p*r*... = N. The Shape is of variable size, not known at compile time.

我要解决的问题是使用整数数组访问地图元素的通用方法，其中各个值是Shape S中的坐标，例如： M [1,3,2]，M [2,3,3,3] 等。是一个与简单枚举地图元素不同的问题。

The issue I'm trying to solve is a generic approach to accessing the map's elements using an array of integers, which individual values are coordinates in the Shape S, ex: M[1,3,2], M[2,3,3,3] etc... This is a problem different from a simple enumeration of the map's elements.

一种方法是使用 M [i，j，k] 并实现下标方法。不幸的是，这种方法对地图的形状进行了硬编码，并且该算法不再通用。

One method is to use M[i,j,k] and implement a subscript method. Unfortunately, this approach hardcodes the map's shape, and the algorithm is no longer generic.

说有一个实用程序函数，该函数从从地图的Shape派生的元组返回元素索引，这样：

Say there's a utility function that returns an element index from a tuple derived from the map's Shape, so that:

func index(_ indexes:[Int]) -> Int {....}

func elementAt(indexes:[Int]) -> Element { 
   return elements_of_the_map[self.index(indexes)]
}

M.elementAt（indexes：[i，j，k]）或M.elementAt（indexes：[i，j，k，l，m]）始终有效。因此，此时的问题是构建数组 [i，j，k，...]

M.elementAt(indexes:[i,j,k]) or M.elementAt(indexes:[i,j,k,l,m]) always work. So the problem at this point is to build the array [i,j,k,...]

问题：是否有一种算法可以有效地枚举那些索引？嵌套循环不起作用，因为在编译时未知循环的数量，而递归函数似乎增加了很多复杂性（特别是跟踪先前的索引）。

Question: Is there an algorithm to efficiently enumerate those indexes? Nested loops won't work since the number of loops isn't known at compile time, and recursive function seem to add a lot of complexity (in particular keeping track of previous indexes).

我正在考虑一种算法'a la'base-x计数，即在右上角的索引处增加一个单位，如果计数超过地图Shape的元素数，则向左移动一个单位。 / p>

I'm thinking about an algorithm 'a la' base-x counting, that is adding one unit to the top right index, and moving leftwards one unit if the count exceeds the number of elements by the map's Shape.

推荐答案

想法相同，但代码更少：

Same idea, but less code:

func addOneUnit(shape: [Int], indexes: [Int]) -> [Int]? {
    var next = indexes
    for i in shape.indices.reversed() {
        next[i] += 1
        if next[i] < shape[i] {
            return next 
        }
        next[i] = 0
    }
    return nil
}

这篇关于使用倍数索引的Swift算法枚举多线性映射：[Int]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！