时间戳

首页 > 解决方案 > 为 LIst 中的元素创建子序列

java - 为 LIst 中的元素创建子序列

问题描述

我正在使用以下代码创建大小为 2 的唯一子序列。如何创建不同大小的子序列。大小将是动态的。

例如，[1 2 3 4] -> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

对于尺寸 3，它将是 , [[1, 2, 3], [1, 2, 4], [2, 3, 4]]

public static int getTheSubseq(List<Integer> AList){
      List<List<Integer>> li = new ArrayList<>();

      for (int i = 0; i < AList.size(); i++){
          for(int j =i+1; j < AList.size(); j++){
              List<Integer> temp = new ArrayList<>();
              temp.add(AList.get(i));
              temp.add(AList.get(j));
              li.add(temp);

          }
      }
      System.out.println(li);
      return 1;

    }

标签： java

解决方案

使用递归，您可以按如下方式构建子序列：

private void buildSubsequence( List<Integer> source, int targetSize,
                                      List<List<Integer>> result, Stack<Integer> currentSubsequence, int currentIndex ) {

    //We don't want to iterate beyond the point where we can't build a complete subsequence.
    //Thus we'll need to subtract the number of still needed elements 
    //(target count - number of elements already in the subsequence - 1 for this call)
    int maxIndex = source.size() - ( targetSize - currentSubsequence.size() - 1);

    //iterate over each index from the current one to this call's max
    for( int i = currentIndex; i < maxIndex; i++ ) {

      //add the element at that index to the subsequence
      currentSubsequence.push( source.get( i ) );

      //if we're done make a copy
      if( currentSubsequence.size() == targetSize ) {
        result.add( new ArrayList<Integer>( currentSubsequence) );
      } else { //if we're not done, get the next element 
        buildSubsequence( source, targetSize, result, currentSubsequence, i + 1 );
      }

      //remove the last element added by push() to have it replaced with the next one
      currentSubsequence.pop();
    }
  }

然后你这样称呼它：

List<Integer> source = Arrays.asList( 1,2,3,4,5,6 );
List<List<Integer>> result = new LinkedList<>();

buildSubsequence( source, 3, result, new Stack<>(), 0 );

这将创建以下子序列：

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
[1, 5, 6]
[2, 3, 4]
[2, 3, 5]
[2, 3, 6]
[2, 4, 5]
[2, 4, 6]
[2, 5, 6]
[3, 4, 5]
[3, 4, 6]
[3, 5, 6]
[4, 5, 6]

请注意，这只是解决问题的一种方法。:)

推荐阅读