m元素集合的n個元素子集

轉載至 : m元素集合的n個元素子集



假設有5個元素的集點，取出3個元素的可能子集如下：

{1 2 3}、{1 2 4 }、{1 2 5}、{1 3 4}、{1 3 5}、{1 4 5}、{2 3 4}、{2 3 5}、{2 4 5}、{3 4 5}

這些子集已經使用字典順序排列，如此才可以觀察出一些規則：

1. 如果最右一個元素小於m，則如同碼錶一樣的不斷加1
2. 如果右邊一位已至最大值，則加1的位置往左移
3. 每次加1的位置往左移後，必須重新調整右邊的元素為遞減順序

所以關鍵點就在於哪一個位置必須進行加1的動作，到底是最右一個位置要加1？還是其它的位置？

在實際撰寫程式時，可以使用一個變數positon來記錄加1的位置，position的初值設定為n-1，因為我們要使用陣列，而最右邊的索引值為最大 的n-1，在position位置的值若小於m就不斷加1，如果大於m了，position就減1，也就是往左移一個位置；由於位置左移後，右邊的元素會 經過調整，所以我們必須檢查最右邊的元素是否小於m，如果是，則position調整回n-1，如果不是，則positon維持不變。

實作：C Java Python Scala

• C

#include 
#include 

#define MAX 20

int main(void) {
int m, n;
printf("輸入集合個數 m：");
scanf("%d", &m);
printf("輸入取出元素 n：");
scanf("%d", &n);

int set[MAX];

int i;
for(i = 0; i < i =" 0;" position =" n" position =" n" j =" position" j =" 0;">= m - n + 1)
break;
}

return 0;
}

• Java

import java.util.*;
public class NofM implements Iterable, Iterator {
private int m;
private int[] set;
private boolean first = true;
private int position;

public NofM(int n, int m) {
this.m = m;
position = n - 1;
set = new int[n];
for(int i = 0; i <> iterator() {
return this;
}

public boolean hasNext() {
return set[0] < first =" false;" position =" set.length" i =" position" i =" 0;">

• Python

class NofM:
def __init__(self, n, m):
self.__m = m
self.__first = True
self.__position = n - 1
self.__set = [i + 1 for i in range(n)]
def __iter__(self):
return self

def __next__(self):
if self.__set[0] >= self.__m - len(self.__set) + 1:
raise StopIteration

if self.__first:
self.__first = False
return self.__set
if self.__set[len(self.__set) - 1] == self.__m:
self.__position -= 1
else:
self.__position = len(self.__set) - 1
self.__set[self.__position] += 1
for i in range(self.__position + 1, len(self.__set)):
self.__set[i] = self.__set[i - 1] + 1
return self.__set

for set in NofM(3, 5):
for i in range(len(set)):
print(set[i], end="")
print()

• Scala

class NofM(n: Int, val m: Int) extends Iterator[Array[Int]] {
private var position = n - 1
private var first = true
private val set = (for(i <- 0 until n) yield i + 1).toArray       def hasNext() = {        set(0) < first =" false" position =" if(set(set.length">