Java实现查找数组中k个元素所有组合的算法

悠悠 2023-10-04 08:29 6阅读 0赞

给定一个大小为N的数组，例如`e={'A','B','C','D','E'}` **N = 5**，我们想找到该数组中**k个**元素的所有可能组合。例如，如果**k = 3，**则一种可能的组合是`{'A','B','C'}`。在这里，我们有三种不同的算法来查找数组的*k个*组合。

### 向前-向后算法 ###

在这里，我们有两个数组和两个主要索引**r**＆**i**：

*  数组**e**是元素数组。
 *  数组**指针**，该数组**指针**用于保存所选元素的索引。
 *  索引**i**指向数组**e中的**当前选定元素。
 *  指向**指针**数组中当前位置的索引**r**。
 *  只要**i**＆**r**不超过数组长度，该算法就会通过增加**i**＆**r**来向前移动。
 *  如果**r**到达**指针**数组的最后位置，则会打印一个组合。
 *  如果这两个指数达到其指向数组的最后poisition的algorith将通过减少退步**\[R**值`r--`，并设置**我**用的价值`i = pointer[r]+1`。

![groups\_forwardbackward][groups_forwardbackward]

public static void combination(Object[]  elements, int k){
           
    
    	// get the length of the array
    	// e.g. for {'A','B','C','D'} => N = 4 
    	int N = elements.length;
    	
    	if(k > N){
           
    		System.out.println("Invalid input, K > N");
    		return;
    	}
    		
    	// init combination index array
    	int pointers[] = new int[k];
    	
    
    	int r = 0; // index for combination array
    	int i = 0; // index for elements array
    	
    	while(r >= 0){
           
    	
    		// forward step if i < (N + (r-K))
    		if(i <= (N + (r - k))){
           
    			pointers[r] = i;
    				
    			// if combination array is full print and increment i;
    			if(r == k-1){
           
    				print(pointers, elements);
    				i++;				
    			}
    			else{
           
    				// if combination is not full yet, select next element
    				i = pointers[r]+1;
    				r++;										
    			}				
    		}
    		
    		// backward step
    		else{
           
    			r--;
    			if(r >= 0)
    				i = pointers[r]+1;
    			
    		}			
    	}
    }

### 移位算法 ###

*  该算法比第一个算法更直观。
 *  我们实际上将elements数组分为两种类型的元素：可以选择的k个元素和将被忽略的Nk个元素。
 *  在每次迭代中，我们选择**Nk个**不可忽略的元素。
 *  每次迭代后，我们将忽略元素的位置移动，如下图所示。

![groups\_shifting][groups_shifting]

public static void combination(Object[]  e, int k){
           
    
    	int[] ignore = new int[e.length-k]; // --> [0][0]
    	int[] combination = new int[k]; // --> [][][]
    	
    	// set initial ignored elements 
    	//(last k elements will be ignored)
    	for(int w = 0; w < ignore.length; w++)
    		ignore[w] = e.length - k +(w+1);
    	
    	int i = 0, r = 0, g = 0;
    	
    	boolean terminate = false;
    	while(!terminate){
              
    		
    		// selecting N-k non-ignored elements
    		while(i < e.length && r < k){
           
        			
        		if(i != ignore[g]){
           
        			combination[r] = i;
        			r++; i++;
        		}
        		else{
           	    			
        			if(g != ignore.length-1)
        				g++;	    			
        			i++;
        		}
        	}
        	print(combination, e);
        	i = 0; r = 0; g = 0;
    
        	terminate = true;
        	
        	// shifting ignored indices
        	for(int w = 0 ; w < ignore.length; w++){
           
        		if(ignore[w] > w){
           	    			
        			ignore[w]--;
        			
        			if(w > 0)
        				ignore[w-1] = ignore[w]-1;
        			terminate = false;
        			break;	    			
        		}
        	}
    	}    		
    }

### 递归算法 ###

*  递归算法具有较短的步骤。
 *  在对函数的每次调用中，我们传递元素列表，**k**和累积组合。
 *  然后我们有四个条件：
    
    1.  如果`elements.length < k`然后停止
    2.  如果`k == 1`然后将每个元素添加到累积的组合中
    3.  如果是，`elements.length == k`则将所有元素添加到累积的组合中。
    4.  如果是，`elements.length > k`则对每个元素`e`进行递归调用，以传递元素列表的子列表，`k-1`然后将元素添加`e`到累积的组合中。
 *  如下图所示

![groups\_recursive][groups_recursive]

public static void combination(List<String> e, int k, String accumulated){
           
    
    	// 1. stop
    	if(e.size() < k)
    		return;
    	
    	// 2. add each element in e to accumulated
    	if(k == 1)
    		for(String s:e)
    			print(accumulated+s);
    	
    	// 3. add all elements in e to accumulated
    	else if(e.size() == k){
           
    		for(String s:e)
    			accumulated+=s;
    		print(accumulated);
    	}
    	
    	// 4. for each element, call combination
    	else if(e.size() > k)
    		for(int i = 0 ; i < e.size() ; i++)
    			combination(e.subList(i+1, e.size()), k-1, accumulated+e.get(i));
    	
    }

#### 源代码@ [GitHub][] ####

[groups_forwardbackward]: https://img-blog.csdnimg.cn/img_convert/8ea1d75da1f42cbc92f00fde2fae8756.png
[groups_shifting]: https://img-blog.csdnimg.cn/img_convert/e0b33a1ef924ed8cfb271b5ae7ef1ec2.png
[groups_recursive]: https://img-blog.csdnimg.cn/img_convert/12a5ff3b198be42a545cba93d4067987.png
[GitHub]: https://github.com/hmkcode/Java/blob/master/java-combinations