logo标签列表

多个数组元素的组合

javaarraysarraylist
4

最近我实现了以下代码 假设我有两个数组-

arr1 = [a,b,c]

arr2 = [d,e]

并且应该是这样的，并使其易于理解。
output = [ad,ae,bd,be,cd,ce]

现在假设我有多个数组。
例如：
arr1=[a,b,c]

arr2=[d,e]

arr3=[f,g,h,i]

arrN=[x,y,z,h,o]

output = [adf..x,adf..y and so on]

如何在JAVA中实现这个？请您帮忙。
我的尝试：
for(int i=0;i<arr1.length();i++)
{
for(int j=0;i<arr2.length();j++)
{
System.out.print(arr1[i] + arr2[j] );
}
}
使用4个循环有什么问题？ - Aseem Goyal
这种组合的数学术语是什么？ - Bikash Gyawali
@bikashg：排列组合 - prgSRR
8个回答
4

您可以在Java 8 Stream Api中轻松实现此功能：

String arr1[] = {"a", "b", "c"};
String arr2[] = {"d", "e"};
String arr3[] = {"f", "g", "h", "i"};

List<String> result = Arrays.stream(arr1)
        .flatMap(s1 -> Arrays.stream(arr2)
                .flatMap(s2 -> Arrays.stream(arr3)
                        .map(s3 -> s1 + s2 + s3)))
        .collect(Collectors.toList());
4
这是我尝试从多个数组（容器）中获取组合的方法。
 private List<List<T>> getCombination(int currentIndex, List<TempContainer<T>> containers) {
    if (currentIndex == containers.size()) {
        // Skip the items for the last container
        List<List<T>> combinations = new ArrayList<List<T>>();
        combinations.add(new ArrayList<T>());
        return combinations;
    }
    List<List<T>> combinations = new ArrayList<List<T>>();
    TempContainer<T> container = containers.get(currentIndex);
    List<T> containerItemList = container.getItems();
    // Get combination from next index
    List<List<T>> suffixList = getCombination(currentIndex + 1, containers);
    int size = containerItemList.size();
    for (int ii = 0; ii < size; ii++) {
        T containerItem = containerItemList.get(ii);
        if (suffixList != null) {
            for (List<T> suffix : suffixList) {
                List<T> nextCombination = new ArrayList<T>();
                nextCombination.add(containerItem);
                nextCombination.addAll(suffix);
                combinations.add(nextCombination);
            }
        }
    }
    return combinations;
}

该方法接受一个包含项目的容器列表，例如，容器1将具有[a,b]，而容器2将具有[c,d,e]。该方法可以使用任意数量的容器。 //容器类声明如下：
public class TempContainer<T> {
    private List<T> items; 
    public void setItems(List<T> items) {
       this.items = items;
    }

    public List<T> getItems() {
         return items;
    }
}

请按以下方式调用此方法：

List<String> list1 = new ArrayList<String>();
list1.add("1");
list1.add("2");
List<String> list2 = new ArrayList<String>();
list2.add("3");
list2.add("4");
list2.add("5");
TempContainer container1 = new TempContainer();
container1.setItems(list1);
TempContainer container2 = new TempContainer();
container2.setItems(list2);
List<TempContainer> containers = new ArrayList<TempContainer>(2);
containers.add(container1);
containers.add(container2);
// Get combinations 
List<List<T>> combinations = getCombination(0, containers);
@nazar_art，你在使用4个容器时遇到了什么问题？我已经尝试过使用4个或更多的容器，并且它可以正常工作。 - Priyesh
它出现了“空指针异常”。 - catch23
@nazar_art 请提供堆栈跟踪信息，或者至少告诉我出错代码所在的行号。 - Priyesh
只要所有的列表中至少有一个项目，这对我来说就可以工作。 - Priyesh
将每个源List都包装在TempContainer中有什么意义？ - Holger
1
我有类似的需求，但是需要对不同类型的集合进行操作。这里是Priyesh解决方案的修改版。
注意：我移除了对TempContainer类的依赖。
public class TestCombinations {

@Test
public void test() {

    final List<Object> l1 = new ArrayList<Object>();
    l1.add(1);
    l1.add(2);
    final List<Object> l2 = new ArrayList<Object>();
    l2.add("3");
    l2.add("4");
    l2.add("5");
    final List<Object> l3 = new ArrayList<Object>();
    l3.add(true);
    l3.add(false);

    final List<List<Object>> c = new ArrayList<>(3);
    c.add(l1);
    c.add(l2);
    c.add(l3);

    // Get combinations
    final List<List<Object>> m = this.combine(c);
    System.out.println(m);

}

public List<List<Object>> combine(final List<List<Object>> containers) {
    return this.combineInternal(0, containers);
}

private List<List<Object>> combineInternal(final int currentIndex,
        final List<List<Object>> containers) {
    if (currentIndex == containers.size()) {
        // Skip the items for the last container
        final List<List<Object>> combinations = new ArrayList<>();
        combinations.add(Collections.emptyList());
        return combinations;
    }

    final List<List<Object>> combinations = new ArrayList<>();
    final List<Object> containerItemList = containers.get(currentIndex);
    // Get combination from next index
    final List<List<Object>> suffixList = this.combineInternal(
            currentIndex + 1, containers);

    final int size = containerItemList.size();
    for (int i = 0; i < size; i++) {
        final Object containerItem = containerItemList.get(i);
        if (suffixList != null) {
            for (final List<Object> suffix : suffixList) {
                final List<Object> nextCombination = new ArrayList<>();
                nextCombination.add(containerItem);
                nextCombination.addAll(suffix);
                combinations.add(nextCombination);
            }
        }
    }

    return combinations;
}

}
0

这个怎么样？

package permutor;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.stream.Stream;

public class Permutor<T> {
    private Stream<List<T>> result;

    public Permutor(final Collection<T> first) {
        result = first.stream().map(Collections::singletonList);
    }

    public Permutor<T> with(final Collection<T> next) {
        result = result.flatMap(list -> next.stream().map(e -> add(list, e)));
        return this;
    }

    private static <T> List<T> add(final List<T> list, final T e) {
        final List<T> result = new ArrayList<>(list);
        result.add(e);
        return result;
    }

    public List<List<T>> getResult() {
        return result.toList();
    }
}

测试：

package permutor;

import static java.util.Arrays.asList;
import static org.assertj.core.api.Assertions.assertThat;

import org.junit.jupiter.api.Test;

class PermutorTest {
    @Test
    void test() {
        final var result = new Permutor<>(asList("a", "b")).with(asList("c")).with(asList("d")).getResult();

        assertThat(result).containsExactly(asList("a", "c", "d"), asList("b", "c", "d"));
    }
}
0

简单就好 -

ArrayList<Integer> combination(int[] ar1, int[] ar2)
{
    ArrayList<Integer> result = new ArrayList<int>();
    for (int i1 : ar1)
    {
        for (int i2 : ar2)
        {
            result.add(i1 * i2);
        }
    }
    return result;
}

嗯，我认为递归是解决一般情况的方法。

import java.util.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        ArrayList<int[]> arrays = new ArrayList<int[]>();
        arrays.add(new int[] { 1, 2, 3 });
        arrays.add(new int[] { 4, 5 });
        arrays.add(new int[] { 6, 7 });

        ArrayList<Integer> result = combination(arrays);
        for (int i : result)
        {
            System.out.println(i);
        }
    }

    static ArrayList<Integer> combination(ArrayList<int[]> arrays)
    {
        if (arrays.size() == 0)
            return null;

        ArrayList<Integer> result = new ArrayList<Integer>();
        combination_sub(arrays, 0, result);
        return result;
    }
    static void combination_sub(ArrayList<int[]> arrays, int idx, ArrayList<Integer> result)
    {
        if (arrays.size() == idx)
        {
            result.add(1);
            return;
        }

        int[] ar = arrays.get(idx);

        ArrayList<Integer> sub_result = new ArrayList<Integer>();
        combination_sub(arrays, idx + 1, sub_result);

        for (int i : ar)
        {
            for (int sub_i : sub_result)
            {
                result.add(i * sub_i);
            }
        }
    }
}
超过2个数组怎么办？ - Maxx
@Shwet 3个数组 -> 3个循环，4个数组 -> 4个循环，...... 您需要多个数组吗？如果是，请稍等片刻... - ikh
1
尝试使用递归处理更多的数组。 - StaNov
有几个数组。对于3个和4个数组，我们可以分别编写3个和4个循环，但对于多个数组来说，编写那么多循环是困难的。 - Maxx
0

把数组放在一个数组里怎么样：

    String[] arr1 = { "a", "b", "c" };

    String[] arr2 = { "d", "e" };

    String[] arr3 = { "f", "g", "h", "i" };

    String[][] arrays = new String[][] { arr1, arr2, arr3 };

    public void mix(String[][] arrays) {

        if (arrays.length > 0) {
            List<String> result = Arrays.asList(arrays[0]);

            for (int i = 1; i < arrays.length - 1; i++) {
            String[] aux = arrays[i];
            for (int j = 0; j < aux.length; j++) {
                result.add(j, result.get(j) + aux[j]);
            }
            }
        }
    }
0

针对3个数组的情况，如果需要其他数量的数组，可以插入额外的代码。递归解决方案。

/* This code is contributed by Devesh Agrawal and modified for personal solution by prism */
/* contributed by Devesh Agrawal at https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/ */

package com.practice.probabilty;

import java.util.ArrayList;

public class CombinationNumber {

    public static void main(String[] args) {

        int[] arr1 = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int[] arr2 = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int[] arr3 = new int[] {0, 2, 4, 6, 8};

        int[] arr = arr1.clone();

        int r = 3; //amount of digits as need

        int n1 = arr1.length; //amount of all digits provided for composing the number
        int n2 = arr2.length;
        int n3 = arr3.length;


        int[] count = new int[]{0}; //for counting total amount of all combination numbers

        printCombination(arr1, arr2, arr3, arr, n1, n2, n3, r, count);

        System.out.println("Total amount of number = " + count[0]);

    }

    /*
     * arr[] ---> Input Array data[] ---> Temporary array to store current
     * combination start & end ---> Staring and Ending indexes in arr[] index --->
     * Current index in data[] r ---> Size of a combination to be printed
     */
    static void combinationUtil_1(int arr1[], int arr2[], int arr3[], int arr[],
            int n1, int n2, int n3, int r, int index,
            int data[], int i1, int i2, int i3, int[] count) {
        // Print index and i
        // System.out.print("data index = " + index + ", arr i = " + i + ", order  = " + order);
        // Current combination is ready to be printed, print it 

        if (index == r) {
            for (int j = 0; j < r; j++) {
                System.out.print(" " + data[j] + " ");

            }

            System.out.println();
            count[0]++;

            return;
        }

        // When no more elements are there to put in data[] 
        if (i1 >= n1 || i2 >= n2 || i3 >= n3)
            return;

        // current is included, put next at next location 

        if(index == 0)
        {

            data[index] = arr1[i1];

            combinationUtil_1(arr1, arr2, arr3, arr2, n1, n2, n3, r, index + 1, data, i1++, i2, i3, count);

            combinationUtil_1(arr1, arr2, arr3, arr2, n1, n2, n3, r, index, data, i1++, i2, i3, count);



        }else if(index == 1)
        {

            data[index] = arr2[i2];

            combinationUtil_1(arr1, arr2, arr3, arr3, n1, n2, n3, r, index + 1, data, i1, i2++, i3, count);

            combinationUtil_1(arr1, arr2, arr3, arr3, n1, n2, n3, r, index, data, i1, i2++, i3, count);

        }
        else
        {

            data[index] = arr3[i3];

            combinationUtil_1(arr1, arr2, arr3, arr1, n1, n2, n3, r, index + 1, data, i1, i2, i3++, count);

            combinationUtil_1(arr1, arr2, arr3, arr1, n1, n2, n3, r, index, data, i1, i2, i3++, count);

        }
    }

    // The main function that prints all combinations of size r
    // This function mainly uses combinationUtil()
    static void printCombination(int arr1[], int arr2[], int arr3[], int arr[], 
            int n1, int n2, int n3, int r, int[] count) {
        // A temporary array to store all combination one by one
        int data[] = new int[r];

        // Print all combination using temporary array 'data[]'
        combinationUtil_1(arr1, arr2, arr3, arr, n1, n2, n3, r, 0, data, 0, 0, 0, count);
    }

}
0

对于几个数组，在这段代码中有4个数组，使用递归

package com.practice.probabilty;

import java.util.ArrayList;
import java.util.HashMap;

public class Example {

    public static void main(String[] args) {

        int[] arr1 = new int[] {1, 2, 3, 4};
        int[] arr2 = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int[] arr3 = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int[] arr4 = new int[] {1, 3, 5, 7, 9};

        ArrayList<int[]> listOfArray = new ArrayList<int[]>();
        listOfArray.add(arr1);
        listOfArray.add(arr2);
        listOfArray.add(arr3);
        listOfArray.add(arr4);


        int sizeOfList = listOfArray.size();
        int r = sizeOfList;

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < sizeOfList; i++)
        {
            map.put(i, 0);
        }

        int[] count = new int[]{0}; //for counting total amount of all combination numbers

        printCombination(listOfArray, sizeOfList, r, map, count);

        System.out.println("Total amount of number = " + count[0]);

    }

    /*
     * arr[] ---> Input Array data[] ---> Temporary array to store current
     * combination start & end ---> Staring and Ending indexes in arr[] index --->
     * Current index in data[] r ---> Size of a combination to be printed
     */

    static void combinationUtil_1(ArrayList<int[]> listOfArray,
            int sizeOfList, int r, int index,
            int data[], HashMap<Integer, Integer> map, int[] count) {

        if (index == r) {
//System.out.print("--> ");
            for (int j = 0; j < r; j++) {
                System.out.print(" " + data[j] + " ");

            }

            System.out.println();
            count[0]++;

            return;
        }

        for(int i = 0; i < sizeOfList; i++)
        {
            if(map.get(i) >= listOfArray.get(i).length)
                return;
        }

            data[index] = listOfArray.get(index)[map.get(index)];

            combinationUtil_1(listOfArray, sizeOfList, r, index + 1, data, map, count);
            HashMap<Integer, Integer> map1 = new HashMap<Integer, Integer>();
            for(int i = 0; i < sizeOfList; i++)
            {
                if(i == index)
                {
                    map1.put(i, map.get(i) + 1);
                }
                else
                {
                    map1.put(i, map.get(i));
                }
            }


            combinationUtil_1(listOfArray, sizeOfList, r, index, data, map1, count);
            HashMap<Integer, Integer> map2 = new HashMap<Integer, Integer>();
            for(int i = 0; i < sizeOfList; i++)
            {
                if(i == index)
                {
                    map2.put(i, map.get(i) + 1);
                }
                else
                {
                    map2.put(i, map.get(i));
                }
            }

    }

    static void printCombination(ArrayList<int[]> listOfArray, 
            int sizeOfList, int r, HashMap<Integer, Integer> map, int[] count) {
        // A temporary array to store all combination one by one
        int data[] = new int[r];

        // Print all combination using temporary array 'data[]'

        combinationUtil_1(listOfArray, sizeOfList, r, 0, data, map, count);
        //combinationUtil_1(arr1, arr2, arr3, arr, n1, n2, n3, r, 0, data, 0, 0, 0, count);
    }

    /* Driver function to check for above function */

}
/* This code is modified from Devesh Agrawal's */
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接