子集三种生成方法 java

增量构造法

public class Main1 {
static int A[] = new int[1 << 7];
static int da[] = new int[1<<7]; public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
da[i] = sc.nextInt();
} print_subset(n, A, 0,da); } } private static void print_subset(int n, int[] A, int cur,int da[]) {
// 打印当前集合
for(int i=0;i<cur;i++)
System.out.printf("%d ",da[A[i]]);        //如果不加da[]的话,这里输出的是下标值,位向量中同理
System.out.println();
int s = cur>0?A[cur-1]+1:0;        //这个表示最小值的下标,cur不等于0的时候,即cur前面还有下标元素,为了得到全部的子集,所以这里不能漏掉,便从最小的那一个选
  
                            //那为什么A[cur-1]+1就是最小的下标呢,刚刚输出的最后一个下标就是A[cur-1],所以这一个下标+1,即还未选择过的最小下标
for(int i=s;i<n;i++){
A[cur]=i;
print_subset(n, A, cur+1,da);
}
}
}

位向量法

public class Main1 {
static int b[] = new int[1 << 7];
static int da[] = new int[1 << 7]; public static void print(int n, int cur, int b[], int da[]) {
if (cur == n) {
for (int i = 0; i < n; i++) {
if (b[i] == 1)
System.out.printf("%d ", da[i]);
}
System.out.println();
return;
}
b[cur] = 1;
print(n, cur + 1, b, da);
b[cur] = 0;
print(n, cur + 1, b, da);
} public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
for (int i = 0; i < n; i++)
da[i] = sc.nextInt();
print(n, 0, b, da);
}
}
}

二进制法

public class Main1 {
public static void sort(int n,int s,String str){
for(int i=0;i<n;i++)
{
int res = s&(1<<i);//看这2的n次方个数上哪些的位数是1。
if(res != 0)
System.out.print(str.charAt(i));//然后打印子集即可。
}
System.out.println();
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();//从控制台得到字符串
int n = str.length();
for(int i=0;i<(1<<n);i++)//一共有2的n次方个子集
sort(n,i,str);
}
}
上一篇:POJ 1035 代码+具体的目光


下一篇:Spring Boot 中的静态资源到底要放在哪里?