求幂集的Java程序_用比特串法求幂集的java实现

你的名字 2022-10-22 15:57 96阅读 0赞

由于Java中有很方便的 String Integer.toBinaryString(int)，在学习生成子集的时后看到用比特串生成幂集的算法，就想着用java实现一下。幂集在解背包问题的时候还是很有用的，蛮力法，简单粗暴有效，当然仅限较小的实例。

实现如下 PowerSetGenerator.java，其中容器的实现用LinkedHashSet是为了保证集合中元素的位置固定，方便测试：

package powerset;

import java.util.Collection;

import java.util.LinkedHashSet;

import java.util.Iterator;

public class PowerSetGenerator \{

public Collection> getPowerSet(Collection set)\{

Collection> r = new LinkedHashSet>();

int binary = 1<

for(int i=0;i

r.add(getSubSet(set,i));

\}

return r;

\}

private Collection getSubSet(Collection set,int binarySeq)\{

Collection sub = new LinkedHashSet();

int mask = 1 <

Iterator it = set.iterator();

while(it.hasNext())\{

T obj = it.next();

mask >>>= 1;

if((binarySeq & mask)!=0)\{

sub.add(obj);

\}

\}

return sub;

\}

\}

groovy单元测试 PowerSetTest.groovy，相当方便，特别是构建集合：

package powerset;

import static org.junit.Assert.\*;

import java.util.HashSet;

import java.util.Set;

import org.junit.Test;

class PowerSetTest \{

static def set = \[1,2,3\]

static Set result = \[\[\], \[3\], \[2\], \[2, 3\], \[1\], \[1, 3\], \[1, 2\], \[1, 2, 3\]\]

static def set2 = \[1,2,3,4\]

static Set result2 = \[\[\], \[4\], \[3\], \[3, 4\], \[2\], \[2, 4\], \[2, 3\], \[2, 3, 4\], \[1\], \[1, 4\], \[1, 3\], \[1, 3, 4\], \[1, 2\], \[1, 2, 4\], \[1, 2, 3\], \[1, 2, 3, 4\]\]

static def set3 = \[1\]

static Set result3 = \[\[\], \[1\]\]

@Test

public void test() \{

PowerSetGenerator generator = new PowerSetGenerator();

assertEquals(result.toString(),generator.getPowerSet(set).toString());

assertEquals(result2.toString(),generator.getPowerSet(set2).toString());

assertEquals(result3.toString(),generator.getPowerSet(set3).toString());

\}

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，96人围观）

还没有评论，来说两句吧...

相关阅读

相关 JavaScript 中的求幂：初学者指南

介绍求幂是指将一个数乘以另一个数的幂的数学过程。例如，如果我们求2的次方3，我们将其计算为2 \ 2 \ 2，这会得到的结果8。在 JavaScript 中，

亦凉/ 2024年03月16日 22:35/ 0 赞/ 18 阅读

相关（C++）设计算法求集合｛1,2,...,n｝的幂集

集合A的幂集是由集合A的所有子集所组成的的集合。如：A=\{1，2，3\}，则A的幂集P（A）=\{ \{1，2，3\}，\{1，2\}，\{1，3\}，\{1\}，\{2

╰+哭是因爲堅強的太久メ/ 2023年02月26日 08:24/ 0 赞/ 66 阅读

相关求幂集的Java程序_用比特串法求幂集的java实现

由于Java中有很方便的 String Integer.toBinaryString(int)，在学习生成子集的时后看到用比特串生成幂集的算法，就想着用java实现一下。幂集在

你的名字/ 2022年10月22日 15:57/ 0 赞/ 97 阅读

相关数据结构单链表应用:回溯法求幂集

include <stdio.h> include <stdlib.h> include <iostream.h> defin

ゝ一世哀愁。/ 2022年09月19日 01:53/ 0 赞/ 66 阅读

相关求高精度幂

<table style="font-family:Simsun"> <tbody> <tr> <td> <div style="text-alig

分手后的思念是犯贱/ 2022年08月01日 11:15/ 0 赞/ 125 阅读

相关 First集和Follow集的求法

对于终结符和非终结符的理解：终结符：通俗的说就是不能单独出现在推导式左边的符号，也就是说终结符不能再进行推导。非终结符：不是终结符的都是非终结符。如：A->B，则A

冷不防/ 2022年06月15日 03:22/ 0 赞/ 156 阅读

相关求幂

东东对幂函数运算很感兴趣，在学习的过程中东东发现了一些有趣的性质：9^3=27^2,2^10 = 32^2.东东对这个性质充满了好奇，东东现在给出一个整数n，希望你能帮助他求出

左手的ㄟ右手/ 2022年06月08日 08:41/ 0 赞/ 151 阅读

相关求高精度幂

周末闲着没事看了下acm的题目，要求计算高精度幂，即一个数的n次幂。代码中的大数用STL中的string表示本文所实现的方法效率不一定达到acm的要求(没有进行性能测试)

朴灿烈づ我的快乐病毒、/ 2022年05月14日 10:59/ 0 赞/ 156 阅读

相关快速求幂算法Java实现

文章目录快速求幂算法inJava 一、累乘二、化繁为简求幂快速求幂算法inJava 一、累乘最

╰半夏微凉°/ 2022年03月01日 06:38/ 0 赞/ 209 阅读

相关高次幂求模

主要的思想是来自一个公式：a\b%c = (a%c) \(b%c) %c 基本概念及思想对形如a^b mod m 的运算（b一般较大）但a,b,m都在lo

淡淡的烟草味﹌/ 2022年02月09日 09:27/ 0 赞/ 445 阅读