如何迭代独立选择的每个排列

假设我有一个列表[x1, x2, x3]，其中x1、x2和x3可以取1到5之间的任何值。

我想迭代所有可能创建的列表（从[1, 1, 1]、[1, 1, 2]、.to [5, 5, 5]）。这是一个简单的问题，列表中只有3个元素。

你可以这样做：

for x = 1; x <= 5; x++;
    for y = 1; y <= 5; y++;
        ...
          for q = 1; q <= 5; q++;
              create list [x, y, ..., q];
              do something with the list;

然而，当元素数量超过10时，如何迭代每个可能的列表？

Edi：我添加了Java作为约束。我只是想看看如果没有太多花哨的图书馆电话，该怎么做。

编辑2：我真正想要的是一些算法，而不是什么样的库可以用来做这件事。但我想要的是一个真正独立于语言的算法。

逻辑：在arr[x1 x2 x3]中；所有x1、x2、x3可以具有从1到5的值。这意味着数组中的每个位置都可以具有从1到5的值。对于当前位置的值，所有值在下一个位置都是可能的。

假设存储的数组值的0位置为1。

表示没有值。

下一个位置的值：[1 1 _]，[1 2 _]，[13 _]，[11 3 _]、[1 4 _]、[15 _]。

因此，在当前位置上迭代以在当前位置存储从1到5的不同可能值，并且对于每个值，再次调用置换函数，使当前位置值增加1，以便在下一位置迭代从1到五的所有可能值。

代码：

public class permutation {
    static int limit;
    public static void permutate(int arr[],int curPos)
    {
        int i;
        if(curPos==arr.length)
        {
            for(i=0;i<arr.length;i++)
            {
                System.out.print(arr[i] + "t");
            }
            System.out.println("");
            return;
        }
        for(i=1;i<=limit;i++)
        {
            arr[curPos]=i;
            permutate(arr,curPos+1);
        }  
    }

    public static void main(String[] args) {
        int arr[] = new int[3];
        limit = 5;
        permutate(arr,0);
    }
}

输出：

使用Guava可以轻松完成：

     public static void main(String[] args) {
         int lowerBound = 1;
         int upperBound = 5;
         int setSize=3;
         ContiguousSet<Integer> integers = ContiguousSet.create(Range.closed(lowerBound, upperBound), DiscreteDomain.integers());
         List<Set<Integer>> sets = Lists.newArrayList();
         for (int i = 0; i < setSize; i++) {
             sets.add(integers);
         }
         Set<List<Integer>> cartesianProduct = Sets.cartesianProduct(sets);
         for (List<Integer> list : cartesianProduct) {
             System.out.println(list);
         }
     }

打印：

[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 1, 5]
...  
[5, 5, 4]
[5, 5, 5]

至少在python中（如果是约束，则应指定语言）：

>>> from itertools import permutations as permu
>>> for i in permu(range(5), 3):
...     print i 
... 
(0, 1, 2)
(0, 1, 3)
(0, 1, 4)
(0, 2, 1)
(0, 2, 3)
(0, 2, 4)
(0, 3, 1)
....

在递归解决方案中，您不必每次都对列表进行排序。将排序列表提供给递归函数必须有效
为此，我编写了这段C#代码。输出结果的长度将由len决定。请记住，输入长度必须等于或大于len:

// Input must be sorted, Result must be initialized to empty list
void Iterate(List<int> input, int len, List<int> result)
{
  if(result.Count == n)
    print result
  else
    foreach (var i in input)
      Iterate(input, len, result.Append(num).ToList())
}

使用此算法。

输入：X是最小数，Y是最大数，Z是独立选择数。

创建一个大小为Z的数组，每个元素等于X。称之为置换
循环：
- 将排列的副本添加到排列列表中
- 将J设置为Z减1
- 循环：
  - 在置换[J]中加1。如果置换[J]现在是Y或更小，则中断
  - 将置换[J]设置为X
  - 从J中减去1。如果J现在小于0，则返回排列列表

必须是经典算法。但是从头开始写总是很有趣的。这里是接受数据集和结果列表大小参数的Java类。核心方法是generate（）。此外，列表可能会根据需要进行复制（更具功能性）。

import com.google.common.collect.Maps;
import org.apache.commons.lang.ArrayUtils;
import java.util.Map;
public class PermutationGenerator {
    private int listValuesSize;
    private int resultListSize;
    private String[] currentList;
    private Map<String, String> nextValue = Maps.newHashMap();
    private int permutations = 0;
    public PermutationGenerator(String[] dataSet, int resultListSize) {
        this.listValuesSize = dataSet.length;
        this.resultListSize = resultListSize;
        init(dataSet);
    }
    private void init(String[] dataSet) {
        // rolling values
        String previous = dataSet[0];
        for (int valuesIndex = 1; valuesIndex < dataSet.length; valuesIndex++) {
            nextValue.put(previous, dataSet[valuesIndex]);
            previous = dataSet[valuesIndex];
        }
        nextValue.put(dataSet[dataSet.length - 1], dataSet[0]);
        // init
        currentList = new String[resultListSize];
        for (int i = 0; i < resultListSize; i++) {
            currentList[i] = dataSet[0];
        }
    }
    public void generate() {
        generate(0, resultListSize - 1);
    }
    private void generate(int from, int to) {
        if (from > to) {
            return;
        }
        for (int i = 0; i < listValuesSize; i++) {
            if (from == to) {
                processList(currentList);
            } else {
                generate(from + 1, to);
            }
            roll(from);
        }
    }
    private void roll(int position) {
        currentList[position] = nextValue.get(currentList[position]);
    }
    private void processList(String[] list) {
        permutations++;
        System.out.println(ArrayUtils.toString(list));
    }
    public static void main(String... args) {
        PermutationGenerator generator = new PermutationGenerator(new String[]{"1", "2", "3", "4", "5"}, 3);
        generator.generate();
        System.out.println(generator.permutations);
    }
}

相关内容

最新更新

热门标签：