黑马程序员技术交流社区

标题: 求问关于数组分组的问题 [打印本页]

作者: OCTSJimmy 时间: 2014-11-11 17:05
标题: 求问关于数组分组的问题
一个问题毫无头绪，特来求救，问题是这样子的，有一个数组，该数组中的数字是连续的自然数，现要将该数组分成两个子数组，请输出所有有可能的划分方法。该数组最小的数一定是1，最大的数不超过50。输出结果不要求顺序。

例如有数组：{1, 2, 3}
输出结果为：
a组:1 b组:2 3
a组:2 b组:1 3
a组:3 b组:1 2

再例如有数组：{1, 2, 3, 4}
那么输出结果为：
a组:1 b组:2 3 4
a组:2 b组:1 3 4
a组:3 b组:1 2 4
a组:4 b组:1 2 3
a组:1 2 b组:3 4
a组:1 3 b组:2 4
a组:1 4 b组:2 3

只求解题思路，万分感谢。

作者: cs8630323 时间: 2014-11-11 17:22
例如有数组：{1, 2, 3}
输出结果为：
a组:1 b组:2 3
a组:2 b组:1 3
a组:3 b组:1 2

a组1 2 b组3 这样不行？？

作者: 冥夜 时间: 2014-11-11 17:33
这个就是求全组合排列的问题啊- -思路：假设共有初始数组有x个元素，那么创建一个二进制数，0表示为0组，1表示为2组。从1，10，11。。这样取，然后取到（int）数组的长度/2。大体是这样。

作者: OCTSJimmy 时间: 2014-11-11 18:43
有思路了，用递归{:3_61:}（严重PS：我极度厌恶递归）

设函数comb（int m，int k)是找出1,2，.....m中任取k个数的所有组合，当组合的第一个数字选定后，其后的数字的就是从余下的m-1个数选k-1个数的组合，问题转化为求comb（m-1, k-1).

需要一个全局数组存放结果，将确定的k个数字组合的第一个数存储在a[k]中，求出一个组合后输出a数组中的一个组合。每个组合的第一个数字可以是m,m-1,.....k.函数确定组合的第一个数字后，如果还为确定组合的其余元素，则继续递归，否则输出。

从提供数组中摘出了一部分的元素分为一个子集数组，剩下的自然就是另一个数组了。

作者: hanxing 时间: 2014-11-12 00:04
这个可以用上次杨哥求最大字符串公共子字符串的思想解决,比那还简单点好像

作者: OCTSJimmy 时间: 2014-11-12 00:16
本帖最后由 OCTSJimmy 于 2014-11-12 00:17 编辑

hanxing 发表于 2014-11-12 00:04
这个可以用上次杨哥求最大字符串公共子字符串的思想解决,比那还简单点好像 ...

嗯，你说的我理解，应该是这样的概念吧，首先有一个字符串abcdefg，再有另一个字符串ccddefsdfabcdesdfsdfk，然后求它们的最大公共子串？

好像与我的题目不一样，我的题目其实也可以转化为：任意一个字符串，字符串中的任意字符均不重复，分成两部分（并非单纯的切割），两部分均不能为空，输出所有有可能的组合。只是题目加了些限制。

例如字符串：abc 可以分为：
a 单独一组 bc为一组也可以分为 b单独一组 ac一组，同时最后也可能分为c单独一组，ab一组。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2