关于集合划分的问题 - ITeye问答

问答首页 → 移动开发技术

0 0

关于集合划分的问题15

求一算法
求集合的全部划分
比如给出一个集合{a,b,c}
他的划分有
{{a},{b},{c}}
{{a,b},{c}}
{{a},{b,c}}
{{a,c},{c}}
{a,b,c}
在下想了很久都没有思路
大家给个思路啊
先谢过了~

2008年8月01日 12:16

zhoujj303030
4
0 0 0

1个答案按时间排序按投票排序

0 0

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class SetPartition
{
    public static void main(String[] args) 
    {
        String[] strArray = {"a", "b", "c", "d", "e"};
        Set strSet = new TreeSet(Arrays.asList(strArray));

        List partitionList = createPartitionList(strSet);
        outputPartitionList(partitionList);
    }

    private static void outputPartitionList(List partitionList)
    {
        for (int i = 0 ; i < partitionList.size() ; i++)
        {
            System.out.print("{");
            List partition = (List)partitionList.get(i);
            for (int j = 0 ; j < partition.size() ; j++)
            {
                System.out.print((j > 0 ) ? ", "  : "");
                System.out.print("{");
                List strList = (List)partition.get(j);
                for (int k = 0 ; k < strList.size() ; k++)
                {
                    System.out.print((k > 0 ) ? ", "  : "");
                    System.out.print(strList.get(k));
                }
                System.out.print("}");
            }
            System.out.println("}");
        }
    }

    /**
     * parm   set Set＜String＞
     * return List＜List＜List＜String＞＞＞
     */
    public static List createPartitionList(Set strSet)
    {
        if (strSet == null 
            || strSet.size() == 0
        ){
            return Collections.EMPTY_LIST;
        }

        List strList = new ArrayList(strSet);
        String firstStr = (String)strList.get(0);

        List firstSet = new ArrayList();
        firstSet.add(firstStr);

        List firstPartition = new ArrayList();
        firstPartition.add(firstSet);

        List partitionList = new ArrayList();
        partitionList.add(firstPartition);

        for (int i = 1 ; i < strList.size() ; i++)
        {
            String str = (String)strList.get(i);
            outputPartitionList(partitionList);
            System.out.println("\n***************************\n");
            partitionList = createNextPartitionList(partitionList, str);
        }
        return partitionList;
    }

    private static List createNextPartitionList(List partitionList, String str)
    {
        List oneStrList = new ArrayList();
        oneStrList.add(str);

        List result = new ArrayList();

        for (int i = 0 ; i < partitionList.size() ; i++)
        {
            List partition = (List)partitionList.get(i);
            int size = partition.size();
            for (int j = 0 ; j < size ; j++)
            {
                List newPartition = new ArrayList(partition);
                List strList = new ArrayList((List)newPartition.get(j));
                strList.add(str);
                newPartition.add(j, strList);
                newPartition.remove(j + 1);
                result.add(newPartition);
            }
            List lastPartition = new ArrayList(partition);
            lastPartition.add(oneStrList);
            result.add(lastPartition);
        }
        return result;
    }
}

引用

{{a}}

***************************

{{a, b}}
{{a}, {b}}

***************************

{{a, b, c}}
{{a, b}, {c}}
{{a, c}, {b}}
{{a}, {b, c}}
{{a}, {b}, {c}}

***************************

{{a, b, c, d}}
{{a, b, c}, {d}}
{{a, b, d}, {c}}
{{a, b}, {c, d}}
{{a, b}, {c}, {d}}
{{a, c, d}, {b}}
{{a, c}, {b, d}}
{{a, c}, {b}, {d}}
{{a, d}, {b, c}}
{{a}, {b, c, d}}
{{a}, {b, c}, {d}}
{{a, d}, {b}, {c}}
{{a}, {b, d}, {c}}
{{a}, {b}, {c, d}}
{{a}, {b}, {c}, {d}}

***************************

{{a, b, c, d, e}}
{{a, b, c, d}, {e}}
{{a, b, c, e}, {d}}
{{a, b, c}, {d, e}}
{{a, b, c}, {d}, {e}}
{{a, b, d, e}, {c}}
{{a, b, d}, {c, e}}
{{a, b, d}, {c}, {e}}
{{a, b, e}, {c, d}}
{{a, b}, {c, d, e}}
{{a, b}, {c, d}, {e}}
{{a, b, e}, {c}, {d}}
{{a, b}, {c, e}, {d}}
{{a, b}, {c}, {d, e}}
{{a, b}, {c}, {d}, {e}}
{{a, c, d, e}, {b}}
{{a, c, d}, {b, e}}
{{a, c, d}, {b}, {e}}
{{a, c, e}, {b, d}}
{{a, c}, {b, d, e}}
{{a, c}, {b, d}, {e}}
{{a, c, e}, {b}, {d}}
{{a, c}, {b, e}, {d}}
{{a, c}, {b}, {d, e}}
{{a, c}, {b}, {d}, {e}}
{{a, d, e}, {b, c}}
{{a, d}, {b, c, e}}
{{a, d}, {b, c}, {e}}
{{a, e}, {b, c, d}}
{{a}, {b, c, d, e}}
{{a}, {b, c, d}, {e}}
{{a, e}, {b, c}, {d}}
{{a}, {b, c, e}, {d}}
{{a}, {b, c}, {d, e}}
{{a}, {b, c}, {d}, {e}}
{{a, d, e}, {b}, {c}}
{{a, d}, {b, e}, {c}}
{{a, d}, {b}, {c, e}}
{{a, d}, {b}, {c}, {e}}
{{a, e}, {b, d}, {c}}
{{a}, {b, d, e}, {c}}
{{a}, {b, d}, {c, e}}
{{a}, {b, d}, {c}, {e}}
{{a, e}, {b}, {c, d}}
{{a}, {b, e}, {c, d}}
{{a}, {b}, {c, d, e}}
{{a}, {b}, {c, d}, {e}}
{{a, e}, {b}, {c}, {d}}
{{a}, {b, e}, {c}, {d}}
{{a}, {b}, {c, e}, {d}}
{{a}, {b}, {c}, {d, e}}
{{a}, {b}, {c}, {d}, {e}}

2008年8月01日 18:59

armorking
152
0 0 0

添加评论

相关推荐

集合划分问题 c++实现: 一个简单的集合划分算法，而且实现效率较高，欢迎下载，本人菜鸟，多多指教

1.9 集合划分问题: 集合划分问题是一个经典的计算机科学问题，它涉及到将一组对象或元素划分为若干个不相交的子集，每个子集都是非空的，并且所有对象都恰好属于一个子集。在编程领域，这个问题通常用于数据处理、算法设计以及优化等...

算法（c++)—— 集合划分问题.rar: 本压缩包文件“算法（c++）—— 集合划分问题.rar”可能包含了一个关于如何用C++解决集合划分问题的实例或教程。集合划分问题描述为：给定一个无序的元素集合，目标是将这些元素划分为若干个非空子集，使得每个...

实现2-7集合划分问题.cpp: 实现2-7集合划分问题.cpp

集合划分问题 java实现: 集合划分问题 Java 实现集合划分问题是计算机科学和数学领域中一个重要的问题，它是指将一个集合划分成多个非空子集的所有可能的方式。这种问题在许多领域都有应用，如数据挖掘、机器学习和数据库管理等。在 ...

集合划分问题: N个元素的集合{1,2,3...,n}可以划分为若干个非空子集。例如，当n=2时，集合{1,2,3}可以划分为2个不同的非空子集如下：{{1}，{2}}，{{1,2}}。编程任务：给定正整数N，计算出N个元素的集合{1,2,3，.....n}可以划分为...

集合划分算法java源码: 总的来说，这个Eclipse项目提供了一个实用的工具，可以帮助开发者理解集合划分的概念，并在实际问题中应用这个算法。通过深入研究源码，不仅可以学习到集合划分的算法实现，还能提升Java编程技巧，尤其是处理递归和...

动态规划集合划分: ### 动态规划在集合划分问题中的应用 #### 一、问题背景与描述本问题主要探讨了如何利用动态规划解决集合划分的问题。具体来说，对于一个包含`n`个元素的集合`{1,2,...,n}`，我们需要计算其能够划分为多少个不同...

集合划分_集合划分问题_silencey5x_depthb1p_4321_: 标题"集合划分_集合划分问题_silencey5x_depthb1p_4321_"中，“集合划分问题”是主要讨论的主题，而“silencey5x_depthb1p_4321”可能是一个特定的算法、代码库或者项目标识，用于标记这个问题的某个具体实例或研究...

集合的划分应用: 它在组合数学中有广泛的应用，尤其是在解决集合划分问题时尤为重要。 **2. 计算公式** 对于任意\(n, k \in \mathbb{N}^+\)，第二类斯特林数\(S(n, k)\)的递推公式为： \[S(n, k) = kS(n-1, k) + S(n-1, k-1)\] ...

集合划分：包含n个元素的集合划分为正好k个非空集合c: 集合划分：包含n个元素的集合划分为正好k个非空子集的方法的数目

集合划分问题C语言实现: 非常完美，它的时间空间复杂度很小，我上大二时编的

spp问题_集合划分问题NPhard_深度学习_: 标题中的“spp问题_集合划分问题NPhard_深度学习_”指的是一个与集合划分问题（Set Partitioning Problem, 简称SPP）相关的项目，它利用深度学习技术来处理这一NPhard问题。NPhard问题是指那些在多项式时间内难以...

集合划分问题的粒子群优化算法.pdf: 在计算机科学与工程领域中，集合划分问题是一个被广泛研究的经典问题，它在诸如多处理机调度、存储分配、财产分割等实际场景中扮演着重要角色。该问题的核心在于如何将一个包含m个正数的集合A划分为T个互不相交的子...

集合划分问题（matlab输出不同的集合）: 集合 X 的划分是 X 的非空子集的集合，使得所有 X 的元素 x 都精确在这些子集的其中一个内。等价的说，X 的子集的集合 P ... 本文件利用matlab解决了该集合划分问题，通过对集合内的元素个数的设置获取不同集合个数。

论文研究-集合划分问题的分布估计求解.pdf: 参考独立分量分析（ICA with Reference，ICA-R）充分利用先验知识或参考信号，取得了很好的分离效果，但其中的阈值参数很难选取，且计算量很大。理论分析和实验表明，若阈值选取不当，算法甚至不收敛。...

小波图像集合划分编码压缩方法: 小波图像集合划分编码压缩方法小波图像集合划分编码压缩方法是基于集合划分的小波图像编码的一般过程。该方法首先将图像矩阵分解为多个小波系数矩阵，然后对每个系数矩阵进行集合划分编码，以减小存储空间。在小...

数据结构划分子集问题C语言代码: 问题描述：已知集合A={a1,a2,……an}，及集合上的关系R={ (ai,aj) | ai,aj∈A, i≠j}，其中(ai,aj)表示ai与aj间存在冲突关系。要求将A划分成互不相交的子集A1,A2,……Ak,(k≤n)，使任何子集中的元素均无冲突关系，...

3-9-12集合划分覆盖等价及序关系.ppt: 集合划分比覆盖更严格，它要求集合A的每个元素不仅属于覆盖的子集之一，而且只能属于一个子集。也就是说，子集之间没有交集（Si∩Sj=∅，i≠j）。例如，对于集合A，S6={{a},{b},{c},{d},{e},{f}}是一个划分，因为每...

整数划分问题、具体算法实现: 对于整数划分，基础情况是当n等于0时，表示没有更多的数字需要划分，返回一个空集合。对于n大于0的情况，我们尝试将n减去每一个可能的部分p（1到n），然后对剩下的n-p进行划分。这个过程可以递归进行，直到达到基础...

Ask-but

我的问答 FAQ | 勋章

相关推荐

已解决问题

未解决问题

排行榜

查看全部排名>>

Global site tag (gtag.js) - Google Analytics