`
coconut_zhang
  • 浏览: 542058 次
  • 性别: Icon_minigender_1
  • 来自: 天津
社区版块
存档分类
最新评论

java实现求一个项目集合任意元子集的通用算法

    博客分类:
  • java
 
阅读更多

在关联规则挖掘过程中,经常涉及到求一个频繁项目集的n元子集,在此设计了一个通过位操作映射子集的通用算法。

 import java.util.BitSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class FindSubset {
 private BitSet start;
 private BitSet end;
 private Set<Set<Object>> subsets;
 public FindSubset() {
  this.start = new BitSet();
  this.end = new BitSet();
  this.subsets = new HashSet<Set<Object>>();
 }
 public void execute(int n, Set<Object> items) {
  int size = items.size();
  for (int i = 0; i < n; i++) {
   start.set(i, true);
  }
  for (int i = n; i < size; i++) {
   start.set(i, false);
  }
  for (int i = size - 1; i > size - n; i--) {
   end.set(i, true);
  }
  for (int i = 0; i < size - n; i++) {
   end.set(i, false);
  }
  find(items);
  while (start != end) {
   boolean endBit = start.get(size - 1);
   int last10 = -1;
   int i;
   for (i = size - 1; i > 0; i--) {
    boolean former = start.get(i - 1);
    boolean last = start.get(i);
    if (former == true && last == false) {
     last10 = i - 1;
     break;
    }
   }
   if (i == 0) {
    break;
   } else {
    if (endBit == false) {
     start.set(last10, false);
     start.set(last10 + 1, true);
     find(items);
    } else {
     start.set(last10, false);
     start.set(last10 + 1, true);
     last10 += 1;
     for (int j = last10 + 1; j < size; j++) {
      if (start.get(j)) {
       start.set(j, false);
       start.set(last10 + 1, true);
       last10 += 1;
       find(items);
      }
     }
    }
   }
  }
 }
 public void find(Set<Object> items) {
  Set<Object> temp = new HashSet<Object>();
  Object elements[] = items.toArray();
  for (int i = 0; i < elements.length; i++) {
   if (start.get(i)) {
    temp.add(elements[i]);
   }
  }
  subsets.add(temp);
 }
 public Set<Set<Object>> getSubsets() {
  return this.subsets;
 }
 
 public void clearSubsets(){
  this.subsets.clear();
 }
 public static void main(String[] args) {
  Set<Object> items = new HashSet<Object>();
  items.add("A");
  items.add("B");
  items.add("C");
  items.add("D");
  items.add("E");
  items.add("F");
  FindSubset fs = new FindSubset();
  for (int i = 0; i < items.size(); i++) {
   System.out.println((i + 1) + "元子集:");
   fs.execute(i + 1, items);
   Iterator<Set<Object>> iterator = fs.getSubsets().iterator();
   while (iterator.hasNext()) {
    Object[] subset = iterator.next().toArray();
    System.out.print("{");
    for (int j = 0; j < subset.length - 1; j++) {
     System.out.print(subset[j] + ",");
    }
    System.out.print(subset[subset.length - 1]);
    System.out.println("}");
   }
   
   fs.clearSubsets();
  }
 }

 

 

测试结果:

 

1元子集:
{D}
{E}
{F}
{A}
{B}
{C}
2元子集:
{D,E}
{F,C}
{E,C}
{F,B}
{E,F}
{D,F}
{A,B}
{B,C}
{D,A}
{A,C}
{D,C}
{E,B}
{F,A}
{D,B}
{E,A}
3元子集:
{E,F,B}
{D,F,C}
{E,F,A}
{D,F,B}
{D,E,C}
{D,E,F}
{E,F,C}
{F,A,B}
{E,A,C}
{D,B,C}
{E,A,B}
{D,A,C}
{F,B,C}
{D,F,A}
{D,E,B}
{F,A,C}
{E,B,C}
{D,E,A}
{D,A,B}
{A,B,C}
4元子集:
{D,E,F,C}
{D,E,F,B}
{E,F,B,C}
{D,E,F,A}
{D,A,B,C}
{E,A,B,C}
{E,F,A,B}
{D,F,A,C}
{D,E,B,C}
{E,F,A,C}
{D,F,B,C}
{F,A,B,C}
{D,E,A,B}
{D,F,A,B}
{D,E,A,C}
5元子集:
{D,E,F,B,C}
{D,E,F,A,C}
{D,E,F,A,B}
{E,F,A,B,C}
{D,F,A,B,C}
{D,E,A,B,C}
6元子集:
{D,E,F,A,B,C}

分享到:
评论

相关推荐

    C/C++ 求一个集合的子集

    C/C++ 求一个集合的子集,代码易懂,好用,谢谢下载

    c++程序设计实现集合交集并集差集.docx

    c++程序设计实现集合交集并集差集.docx

    python 递增的三元子序列(贪心算法)

    # 给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。 # 输入示例 # 输入: [1,2,3,4,5] 输出: true 示例 2: 输入: [5,4,3,2,1] 输出: false # 输出示例 # 输入: [1,2,3,4,5] 输出: true 示例 2...

    C++使用递归算法求交错幂集

    在本文中,我们将深入探讨交错幂集的定义,并通过一个C++程序来理解如何使用递归算法来实现它。 首先,交错幂集P(S)定义为集合S的所有n元子集的集合,其中每个元素x满足x1 ≠ x2,当1 ≤ i ≤ n。这意味着在构造...

    java-leetcode面试题解双指针之第334题递增的三元子序列.zip

    题目是“递增的三元子序列”( Increasing Triplet Subsequence),这是一个典型的算法问题,常出现在数据结构和算法的面试中。下面我们将深入探讨这个问题及其解决方案。 首先,我们要理解什么是三元子序列。在一...

    基于JPBC的SM9算法的java实现

    基于JPBC的SM9算法的java实现,实现SM9算法的所有部分。包括主密钥对的生成,用户私钥生成;签名验签算法,密钥封装解封算法,数据加密解密算法,密钥交换算法;以及对《GMT 0044-2016 SM9标识密码算法:第5部分》...

    递增的三元子序列(python)1

    在给定的编程问题中,任务是检查一个整数数组 `nums` 是否存在递增的三元子序列,即找到三个下标 `i`, `j`, `k` 且满足 `i 使得 `nums[i] [j] [k]`。这是一个经典的动态规划问题,可以通过简单的迭代和比较来解决。 ...

    超越完备元子本原作用系统的均衡交叠对冲分析

    1. 超越完备元子:这可能是文章中的一个核心概念,但当前语境中没有给出明确定义。在物理学中,“元子”一词可能指代基本粒子,但“超越完备元子”这一术语并不是物理学中的标准术语。从字面上理解,“超越”可能...

    集合的概念难题汇编(附答案).doc

    如果一个集合S关于数的乘法是封闭的,意味着集合内任意两个元素的乘积仍属于S。题目给出的T和V是整数集Z的两个不相交子集,且满足特定条件,但没有提供足够的信息来确定哪个集合是乘法封闭的。 2. 题目2引入了一个...

    超越完备元子自旋、对称代数与超越完备元子场

    超越完备元子对称性可能是超对称性在超越完备理论框架下的一个推广或者深化。 6. 高维空间和超引力:在理论物理学中,有一些理论如弦论和M理论,提出了在四维时空之外还存在更多维度的可能性。这些高维理论尝试解释...

    全选主元子程序

    根据提供的信息,我们可以看到这是一段与高斯消元法相关的C语言代码,这段代码实现了一个名为`intrgauss`的函数,用于求解线性方程组。下面将对这段代码进行详细的分析和解释。 ### 标题:全选主元子程序 #### ...

    基于等价二元子图分割的直方图均衡化的彩色图像处理.pdf

    本文提出的等价二元子图分割的直方图均衡化算法,能够针对彩色图像的不同部分进行有针对性的增强,相比传统直方图均衡化,能更好地保留图像细节,避免过度增强导致的失真。这种方法不仅适用于静态图像,还可以应用于...

    算法笔试题:(Python实现)—— 算法面试题汇总

    II实现 Trie (前缀树)单词搜索 II有效的字母异位词字符串中的第一个唯一字符数组Python实现乘积最大子序列多数元素存在重复元素移动零打乱数组两个数组的交集 II递增的三元子序列搜索二维矩阵 II除自身以外数组的...

    PCA-LDA算法

    性别鉴别,作为人脸识别的一个分支,旨在通过分析人脸图像特征来判断个体的性别。这一技术在人机交互系统、公共安全、市场分析等领域有着广泛的应用前景。 **1. 预处理阶段** 预处理是性别分类算法的基础步骤,...

    算法10_NP完全问题1

    【算法10_NP完全问题1】主要探讨的是计算机科学中的一个重要理论领域——NP完全问题。NP完全问题涉及的是在多项式时间内难以解决的一类决策和优化问题,这些问题的复杂性在于,虽然验证一个解决方案可以在多项式时间...

    面阵中二维角度估计 Unitary -ESPRIT算法MATLAB程序

    【标题】中的“面阵中二维角度估计 Unitary -ESPRIT算法MATLAB程序”指的是一个使用MATLAB编程实现的算法,该算法专注于在面阵(array)接收数据的情况下进行二维角度估计。在无线通信、雷达信号处理以及声学等领域...

    一种前向神经网络定值子集训练算法.pdf

    总结来说,前向神经网络定值子集训练算法(FsBT)是一种创新的优化方法,它通过智能选择参与训练的神经元子集,提升了训练效率和模型的拟合精度,从而在深度学习和机器学习领域提供了一种高效的训练工具。这种算法...

    元子,以UGC为支撑,图片+语音模式母婴社区.docx

    【元子社区】是一个以UGC(用户生成内容)为核心的母婴社区平台,主要针对0-6岁儿童的父母,旨在提供一个分享知识、经验和见解的空间。该社区采用了创新的图片+语音模式,允许用户通过拍摄照片并附加语音注解来分享...

Global site tag (gtag.js) - Google Analytics