java中的置换迭代器 [英] Permutation Iterator in java
本文介绍了java中的置换迭代器的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我想要一个类，它接受一个正整数并生成一个迭代器，让我遍历正整数下正数列表的所有可能排列.
例如.permulator p = paemulator(3)
p.next() -> [0,1,2]
p.next() -> [0,2,1]
p.next() -> [1,0,2]
p.next() -> [1,2,0]
...
在这种情况下，这是 6 种可能的排列.我设计了一个类，但它非常慢，我想让迭代速度更快.这是我的设计:
(我这样做是为了这似乎是可能的.)
包 Mathematica.complexity;导入 java.util.Iterator;导入 java.util.LinkedList;导入 java.util.List;导入 java.util.NoSuchElementException;/*** 这将是一个演示我们所说的类:* 阶乘复杂度算法* 它将打印某种集合的所有可能排列* 在 Java 中.* <br>* 类似于排列过程的递归数据结构.* @作者达西**/公共类 FactorialComplexity 实现 Iterator>{私人列表<整数>G_数据；//类的子递归结构.private FactorialComplexity G_next = null;私人 int G_ChoosenIndex = 0;私人布尔 G_canProduceNextElement= true;public static void main(String[] args){}公共因子复杂度(int NumbersofElements){if(NumbersofElements <0)throw new AssertionError();this.G_Data = new LinkedList<>();for(int i =0; i argIn){this.G_Data = argIn;this.prepareSubStructure();}/*** 使用内部索引返回当前元素* 指着.* <br></b>I 不增加内部指针.</b>* @返回*/公共整数 getChoosenElement(){//if(this.G_Data.size() == 0)return null;返回 this.G_Data.get(this.G_ChoosenIndex);}/*** 该函数为迭代器服务.* @返回*/公共列表<整数>getPermutation(){//两个基本情况.if(this.G_Data.size()==0){返回新的 LinkedList();}if(this.G_Data.size()==1){列表<整数>temp = new LinkedList<>();temp.add(this.G_Data.get(0));返回温度；}return this.getPermutation_part1(new LinkedList());}私人列表<整数>getPermutation_part1(List argIn){argIn.add(getChoosenElement());argIn.addAll(this.G_next.getPermutation());返回参数；}/*** <ol>* <li>如果子结构有下一个元素，则增加子结构.* 如果不是，则在此实例中增加索引并重新创建子结构.* <li>请注意基本情况.* </ol>** @返回* 如果这样，包括子结构应该增加.**/受保护的布尔增量(){if(this.G_next!= null){boolean temp = this.G_next.increment();int 指针 = this.G_ChoosenIndex;if(this.G_ChoosenIndex+1下一个(){列表<整数>结果 = this.getPermutation();this.increment();返回结果；}公共字符串 toString(){String s = new String();s+= this.G_Data+":"+this.G_ChoosenIndex+"->";if(this.G_next!= null)s+= this.G_next.toString();返回 s;}/*** <ol>* <li>基本情况:此时的列表为空.* <li>制作本地收藏的副本，不包括* 指针指向的元素* 将 this 对象连接到其子结构并递归.* </ol>*/protected void prepareSubStructure(){if(this.G_Data.size() == 0)return;列表<整数>temp = new LinkedList<>();temp.addAll(this.G_Data);temp.remove(this.G_ChoosenIndex);this.G_next = new FactorialComplexity(temp);this.G_next.prepareSubStructure();}公共静态整数阶乘(int n){if(n<0)返回0；if(n<=1)返回1；返回 n*factorial(n-1);}} 总结:该类像链表一样递归，每个节点都包含一个指示它指向的元素的索引以及从前一个节点传递的所有元素的列表.
这种方法有多天真?我怎样才能让它更快?
解决方案
使用堆算法的实现.它即时计算下一个排列.并且只有一个数组复制
<预><代码>导入 java.util.Arrays;导入 java.util.Iterator;类置换器用法:
<预><代码>公共静态无效主(字符串 [] args){置换器<整数>perm = new PermutatorI want a class, that take in a possitive integer and produce a iterator that let me iterate through all possible of permutation of a list of possitive numbers under the positive integer.
eg. permulator p = paermulator(3)
p.next() -> [0,1,2]
p.next() -> [0,2,1]
p.next() -> [1,0,2]
p.next() -> [1,2,0]
...
which is 6 possible permutations in this case.
I have designed a class, but it is incredibly slow, I want to make iterate faster.
This is my design:
(I am doing it pruely for that sake that it seems possible. )
package Mathematica.complexity;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
/**
* Tthis will be a class that demonstrate what we call:
* a factorial complexity algorithm
* it's going to print all the possible permutations of some sort of collection
* in java.
* <br>
* A recursive data structure that resembles the process of permutating.
* @author dashie
*
*/
public class FactorialComplexity implements Iterator<List<Integer>>
{
private List<Integer> G_Data;
// sub recursive structure of the class.
private FactorialComplexity G_next = null;
private int G_ChoosenIndex = 0;
private boolean G_canProduceNextElement= true;
public static void main(String[] args)
{
}
public FactorialComplexity(int NumbersofElements)
{
if(NumbersofElements <0)throw new AssertionError();
this.G_Data = new LinkedList<>();
for(int i =0; i< NumbersofElements;i++)this.G_Data.add(i);
this.prepareSubStructure();
}
protected FactorialComplexity(List<Integer> argIn)
{
this.G_Data = argIn;
this.prepareSubStructure();
}
/**
* Using the internal index to return the current element it is
* pointing at.
* <br></b>I doesn't increment the internal pointer. </b>
* @return
*/
public Integer getChoosenElement()
{
//if(this.G_Data.size() == 0)return null;
return this.G_Data.get(this.G_ChoosenIndex);
}
/**
* This function serves for the iterator.
* @return
*/
public List<Integer> getPermutation()
{
// two of the base case.
if(this.G_Data.size()==0)
{
return new LinkedList<>();
}
if(this.G_Data.size()==1)
{
List<Integer> temp = new LinkedList<>();
temp.add(this.G_Data.get(0));
return temp;
}
return this.getPermutation_part1(new LinkedList<Integer>());
}
private List<Integer> getPermutation_part1(List<Integer> argIn)
{
argIn.add(getChoosenElement());
argIn.addAll(this.G_next.getPermutation());
return argIn;
}
/**
* <ol>
* <li>If the sub-structure has next element, increment the sub structure.
* <li>If not, increment the index in this instance and recreate sub structure.
* <li>be careful about the base case please.
* </ol>
*
* @return
* if this, including sub structure should be incremented.
*
*/
protected boolean increment()
{
if(this.G_next!= null)
{
boolean temp = this.G_next.increment();
int pointer = this.G_ChoosenIndex;
if(this.G_ChoosenIndex+1<this.G_Data.size())
{
if(temp)
{
this.G_ChoosenIndex++;
this.prepareSubStructure();
}
return false;
}
else
{
return (this.G_ChoosenIndex+1 == this.G_Data.size())&&temp;
}
}
else
{
//empty means not choice can make.
return true;
}
}
@Override
/**
* All the nodes are at its last index.
*/
public boolean hasNext()
{
if(!this.G_canProduceNextElement)return false;
if(this.isAllPointingAtLastIndex())this.G_canProduceNextElement=false;
return true;
}
/**
* This index in this class instance and
* all its sub structure are pointing at the last index?
* @return
*/
boolean isAllPointingAtLastIndex()
{
if(this.G_Data.size()<=1)
{
return true;
}
return this.G_ChoosenIndex+1
==
this.G_Data.size()&&this.G_next.isAllPointingAtLastIndex();
}
@Override
public List<Integer> next()
{
List<Integer> result = this.getPermutation();
this.increment();
return result;
}
public String toString()
{
String s = new String();
s+= this.G_Data+":"+this.G_ChoosenIndex+"->";
if(this.G_next!= null)s+= this.G_next.toString();
return s;
}
/**
* <ol>
* <li>Base case: the list in this instant is empty.
* <li>Make a copy of the local collection, excluding the
* element the pointer is pointing to
* <li>Make connect the this object to its sub structure and recurse.
* </ol>
*/
protected void prepareSubStructure()
{
if(this.G_Data.size() == 0)return;
List<Integer> temp = new LinkedList<>();
temp.addAll(this.G_Data);
temp.remove(this.G_ChoosenIndex);
this.G_next = new FactorialComplexity(temp);
this.G_next.prepareSubStructure();
}
public static int factorial(int n)
{
if(n<0)return 0;
if(n<=1)return 1;
return n*factorial(n-1);
}
}
To summarize: The class is recursive like a linked list, each node contains the an index that indicate the element it is pointing at and a list of all the element got passed from the previouse node.
How Naive is this approach? How can I make it faster?
解决方案
An implementation using Heap's Algorithm. It compute next permutations on the fly. And have only one array copying
import java.util.Arrays;
import java.util.Iterator;
class Permutator<E> implements Iterator<E[]>{
E[] arr1 = null;
E[] arr2 = null;
int size;
int[] stack = null;
int index = 0;
public Permutator( E[] arr ){
if( arr.length > 0 ){
arr1 = arr;
size = arr1.length;
arr2 = Arrays.copyOf(arr1, size);
stack = new int[size];
Arrays.fill(stack, 0);
}
}
@Override
public boolean hasNext() {
return (null != arr1 && arr1.length > 0);
}
@Override
public E[] next() {
// start computing.
// We will return original array as value of last permutation.
// This is to make "hasNext() " implementation easy.
updateValue();
return arr2;
}
protected void updateValue(){
boolean bret = false;
for( ; index < size ; ){
if( stack[index] < index ){
if( index %2 == 0 ){
swap(0, index);
}else{
swap(stack[index], index);
}
stack[index]++;
index = 0;
bret = true;
break;
}else{
stack[index] = 0;
index++;
}
}
if( !bret ){
// No more permutation available.
// Set the original array as return value.
// Also set arr1 = null , so that hasNext() will return false for next test
arr2 = arr1;
arr1 = null;
}
}
private void swap (final int i, final int j) {
E temp = arr2[i];
arr2[i] = arr2 [j];
arr2[j] = temp;
}
}
Usage:
public static void main(String[] args) {
Permutator<Integer> perm = new Permutator<Integer>(new Integer[]{1,2,3, 4, 5});
int count = 0;
while(perm.hasNext()){
System.out.println(Arrays.toString(perm.next()));
count++;
}
System.out.println("total: " + count);
}
这篇关于java中的置换迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
