- 主题:这种组合算法怎么写？
a,b,c,d四个对象
我要生成a,b,c,d的全组合===C(4,1)+C(4,2)+C(4,3)+C(4,4)
结果就是输出 {a,b,c,d, ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd}
这种算法很常见，java有类似的库吗？
--
修改:iStudy FROM 58.37.127.*
FROM 58.37.127.*
import java.util.Arrays;
import java.util.TreeSet;
public class CombinationTest {
public static void main(final String[] args) {
final String[] ss = { "B", "A", "E", "B", "C", "D" };
final String[] arr = new TreeSet<>(Arrays.asList(ss)).toArray(new String[0
]); // 去重
for (int n = 1; n <= arr.length; n++) {
final String[] out = new String[n];
combine(arr, out, 0, 0, n);
}
}
private static void combine(final String[] in, final String[] out, final in
t curIdx, final int level, final int n) {
if (level == n) {
System.out.println(Arrays.toString(out));
return;
}
for (int i = curIdx; i < in.length; i++) {
out[level] = in[i];
combine(in, out, i + 1, level + 1, n);
}
}
}
输出：
[A]
[B]
[C]
[D]
[E]
[A, B]
[A, C]
[A, D]
[A, E]
[B, C]
[B, D]
[B, E]
[C, D]
[C, E]
[D, E]
[A, B, C]
[A, B, D]
[A, B, E]
[A, C, D]
[A, C, E]
[A, D, E]
[B, C, D]
[B, C, E]
[B, D, E]
[C, D, E]
[A, B, C, D]
[A, B, C, E]
[A, B, D, E]
[A, C, D, E]
[B, C, D, E]
[A, B, C, D, E]
【 在 iStudy 的大作中提到: 】
: a,b,c,d四个对象
: 我要生成a,b,c,d的全组合===C(4,1)+C(4,2)+C(4,3)+C(4,4)
: 结果就是输出 {a,b,c,d, ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd}
: ...................
--
FROM 119.233.240.*
大神，能帮我看这修改一下吗？
package test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MySolution5 {
private static List<List<Integer[]>> helper(List<Integer[]> bookSet, int num) {
List<List<Integer[]>> ret = new ArrayList<>();
List<Integer[]> bookSetCombination = new ArrayList<>();
if (num > bookSet.size())
return ret;
if (num == 1) {
for (Integer[] book : bookSet) {
bookSetCombination.add(book.clone());
ret.add(bookSetCombination);
}
return ret;
}
if (num == bookSet.size()) {
for (Integer[] book : bookSet) {
bookSetCombination.add(book.clone());
}
ret.add(bookSetCombination);
return ret;
}
if (num < bookSet.size()) {
List<Integer[]> tmpBookSet = new ArrayList<>(bookSet);
for (int i = 0; i < bookSet.size(); i++) {
bookSetCombination.add(bookSet.get(i).clone());
//注释掉这句，是可以运行的
ret = helper(tmpBookSet, num - 1);
for (List<Integer[]> combination : ret) {
bookSetCombination.addAll(combination);
ret.add(bookSetCombination);
}
}
}
return ret;
}
public static void main(String[] args) {
// {3,10} 是一个book元素，看成一个元素就行了。
// 希望输出结果如下：
// {[3,10]} {[4,20]} {[1,5]}
// {[ 3, 10 ], [ 4, 20 ]} {[ 4, 20 ], [ 1, 5 ]} {[ 3, 10 ], [ 1, 5 ]}
// {[ 3, 10 ], [ 4, 20 ], [ 1, 5 ]}
Integer[][] books1 = new Integer[][] { { 3, 10 }, { 4, 20 }, { 1, 5 } };
List<Integer[]> bookCombination = new ArrayList<Integer[]>(Arrays.asList(books1));
int num = bookCombination.size();
while (num-- >= 0) {
List<List<Integer[]>> ret = helper(bookCombination, num);
for (List<Integer[]> combination : ret) {
for (Integer[] book : combination)
System.out.printf(" %s", Arrays.deepToString(book));
System.out.println();
}
;
}
}
}
【 在 callmebbser 的大作中提到: 】
: import java.util.Arrays;
: import java.util.TreeSet;
: public class CombinationTest {
: ...................
--
修改:iStudy FROM 58.37.127.*
FROM 58.37.127.*
这个helper函数代码少了几行。。我加在这里，我觉得思路很清晰，怎么编译不过呢
private static List<List<Integer[]>> helper(List<Integer[]> bookSet, int num) {
List<List<Integer[]>> ret = new ArrayList<>();
List<Integer[]> bookSetCombination=new ArrayList<>();
if(num>bookSet.size()) return ret ;
if(num==1) {
for (Integer[] book : bookSet)
{
bookSetCombination.add(book.clone());
ret.add(bookSetCombination);
}
return ret;
}
if (num == bookSet.size()) {
for (Integer[] book : bookSet)
{
bookSetCombination.add(book.clone());
}
ret.add(bookSetCombination);
return ret;
}
if (num < bookSet.size()) {
for (int i=0;i<bookSet.size();i++)
{
bookSetCombination.add(bookSet.get(i).clone());
List<Integer[]> tmpBookSet = new ArrayList<>(bookSet);
for(Integer[] tmpBook : tmpBookSet) {
if(tmpBook.equals(bookSet.get(i))) {
tmpBookSet.remove(tmpBook);
}
}
ret=helper(tmpBookSet, num-1);
for(List<Integer[]> combination :ret) {
bookSetCombination.addAll(combination);
ret.add(bookSetCombination);
}
}
}
return ret;
}
【 在 iStudy 的大作中提到: 】
: 大神，能帮我看这修改一下吗？
: package test;
: import java.util.ArrayList;
: ...................
--
修改:iStudy FROM 58.37.127.*
FROM 58.37.127.*
你这个程序太精炼了，不太看得懂。。
用你的例子改了一下，结果不对，哪里错了
package test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MySolution6 {
private static List<List<Integer[]>> helper(List<Integer[]> bookSet,int curIndex,int level, int num) {
List<List<Integer[]>> ret = new ArrayList<>();
List<Integer[]> bookSetCombination=new ArrayList<>();
if(num>bookSet.size()) return ret ;
if(num==1) {
for (Integer[] book : bookSet)
{
bookSetCombination.add(book.clone());
ret.add(bookSetCombination);
}
return ret;
}
if (num == (level+1)) {
for (Integer[] book : bookSet)
{
bookSetCombination.add(book.clone());
}
ret.add(bookSetCombination);
for (List<Integer[]> combination: ret) {
for (Integer[] book : combination)System.out.printf(" %s", Arrays.deepToString(book));
System.out.println();
};
return ret;
}
for (int i = curIndex; i < bookSet.size(); i++) {
bookSetCombination.add(bookSet.get(i));
ret=helper(bookSet, i + 1, level + 1, num);
}
return ret;
}
public static void main(String[] args) {
Integer[][] books1 = new Integer[][] { { 3, 10 }, { 4, 20 }, { 1,5 }, { 2, 40 },{3,40} };
List<Integer[]> bookSet = new ArrayList<Integer[]>(Arrays.asList(books1));
int num=bookSet.size();
while(num-->=0) {
List<List<Integer[]>> ret = helper(bookSet,0,0,num);
for (List<Integer[]> combination: ret) {
for (Integer[] book : combination)System.out.printf(" %s", Arrays.deepToString(book));
System.out.println();
};
}
}
}
【 在 callmebbser 的大作中提到: 】
: import java.util.Arrays;
: import java.util.TreeSet;
: public class CombinationTest {
: ...................
--
修改:iStudy FROM 58.37.127.*
FROM 58.37.127.*
本质就是所有的四位二进制数,1对应出现,0对应不出现
【 在 iStudy 的大作中提到: 】
: a,b,c,d四个对象
: 我要生成a,b,c,d的全组合===C(4,1)+C(4,2)+C(4,3)+C(4,4)
: 结果就是输出 {a,b,c,d, ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd}
: ...................
--
FROM 61.149.70.142
有没有通用一点的样板程序。。。。我依猫画虎，试试
【 在 annals 的大作中提到: 】
: 本质就是所有的四位二进制数,1对应出现,0对应不出现
--
FROM 58.37.127.*
你还是看懂二楼比较好，
--
FROM 50.98.230.*
试试AI？楼上的是自己写的吗
？
--
FROM 120.244.196.*
[Java版]
static List<String> fullCombination(String[] elems) {
List<String> fullElements = new ArrayList<>();
for (String currentElem : elems) {
ListIterator<String> iter = fullElements.listIterator();
while (iter.hasNext()) {
iter.add(iter.next() + currentElem);
}
iter.add(currentElem);
}
return fullElements;
}
public static void main(String[] args) {
String[] elems = {"A", "B", "C", "D"};
List<String> results = fullCombination(elems);
System.out.println(results + "\t total elems: " + results.size());
}
[Python版]
import itertools
elems = ['a', 'b', 'c', 'd']
full_combination = []
for num in range(1, len(elems)+1):
for subset in itertools.combinations(elems, num):
full_combination.append("".join(subset))
print(full_combination)
【 在 iStudy 的大作中提到: 】
: a,b,c,d四个对象
: 我要生成a,b,c,d的全组合===C(4,1)+C(4,2)+C(4,3)+C(4,4)
: 结果就是输出 {a,b,c,d, ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd}
: ...................
--
FROM 135.0.251.*