创建固定大小元素列表中的非重复排列列表
问题描述:
我有一个对象列表M := [A, B, C, ... Z]
,我想创建一个新列表N,其中包含非重复固定大小“f
”这些对象的排列。创建固定大小元素列表中的非重复排列列表
因此n将(for f = 2) [[A, B], [A, C], ...]
,但不应该包含类似[A, A]
重复,如果[A, B]
设置[B, A]
应该被忽略。
我发现事情好像Guavas
“PowerSet
”,但是这不会帮助我,因为它不能被“裁剪”为固定大小。
我希望我已经正确地指出我的问题。
˚F应该始终是以下2
基于http://algorithms.tutorialhorizon.com/print-all-combinations-of-subset-of-size-k-from-given-array/我所做的:
private Set<List<Object>> combineObjects(List<Object> M) {
boolean[] used = new boolean[M.size()];
return generateObjectCombinations(M, 0, 0, used);
}
private Set<List<Object>> generateObjectCombinations(
List<Object> M,
int start,
int curLen,
boolean[] used
) {
Set<List<Object>> returnSet = new HashSet<>();
if (curLen == 2) {
List<Object> data = newArrayList();
for (int i = 0; i < M.size(); i++) {
if (used[i]) {
data.add(M.get(i));
}
}
returnSet.add(data);
return returnSet;
}
if (start == M.size()) {
return Collections.emptySet();
}
used[start] = true;
returnSet.addAll(generateObjectCombinations(M, start + 1, curLen + 1, used));
used[start] = false;
returnSet.addAll(generateObjectCombinations(M, start + 1, curLen, used));
return returnSet;
}
这是工作,但我不知道是否有一个“干净”的解决方案。我想消除布尔数组。
不,这不是我的功课。也许我只是很累,应该休假。
编辑 基于@ azro的回答我重组这样的代码:
List<List<Object>> combinations = new ArrayList<>();
List<Object> M = new ArrayList<>();
for (int i = 0; i < M.size(); i++) {
Object outerM = M.get(i);
for (int j = i; j < M.size(); j++) {
Object innerM = M.get(j);
if (innerM.equals(outerM)) {
continue;
}
combinations.add(Lists.newArrayList(outerM, innerM));
}
}
甚至更好
List<List<Object>> combinations = new ArrayList<>();
List<Object> M = new ArrayList<>();
for (int i = 0; i < M.size(); i++) {
Object outerM = M.get(i);
for (int j = (i + 1); j < M.size(); j++) {
Object innerM = M.get(j);
combinations.add(Lists.newArrayList(outerM, innerM));
}
}
我真的应该采取过长...度假。谢谢@azro!
答
由于您没有写“F应该总是2”开始的时候我写了工程f>=1
,所以这里的方法和如何使用它的解决方案:
public static void main(String[] args) {
List<String> letter = Arrays.asList("A", "B", "C", "D", "E");
List<String> res = new ArrayList<>();
res.addAll(letter);
int size = 2;
for (int i = 1; i < size ; i++) {
res = addLetter(res, letter); //add a letter to all
}
res.forEach(p -> System.out.println(p));
}
public static List<String> addLetter(List<String> already, List<String> letters) {
List<String> res = new ArrayList<>();
for (String al : already) {
for (String let : letters) {
if (!al.contains(let)) {
res.add(al + let);
}
}
}
return res;
}
如果“F应该总是2”你只需要:
public static void main(String[] args) {
List<String> letters = Arrays.asList("A", "B", "C", "D", "E");
List<String> res = new ArrayList<>();
for (String al : letters) {
for (String let : letters) {
if (!al.contains(let)) {
res.add(al + let);
}
}
}
res.forEach(p -> System.out.println(p));
}
+0
感谢@azro。 –
答
我不知道这是否是最好的解决办法,但你在这里:
static HashSet<HashSet<String>> getCombinations(HashSet<HashSet<String>> s, int f)
{
if(f == 1)
return s;
HashSet<HashSet<String>> newSet = new HashSet<HashSet<String>>();
for (HashSet<String> ss : s)
{
for(String elm : A)
{
if(ss.contains(elm))
continue;
HashSet<String> sss = (HashSet<String>)ss.clone();
sss.add(elm);
newSet.add(sss);
}
}
return getCombinations(newSet, f-1);
}
用法:
String[] A = {"A", "B", "C", "D", "E"};
public static void main(String[] args)
{
int f = 3;
HashSet<HashSet<String>> set = new HashSet<>();
for(String s : A)
{
HashSet<String> ss = new HashSet<>();
ss.add(s);
set.add(ss);
}
System.out.println(getCombinations(set, f));
}
不是真的 - 你有什么问题吗? –
显示一些事情,你已经做了但 – azro
我知道你的意思。这很简单..你需要的只是在Foreach循环中有字母的数组和Foreach循环。 – Bernhard