0

我知道有很多类似的问题，我已经阅读了几个小时。但似乎没有一个符合我的要求。

我有列表列表（列表<列表<字符串>>）列表可以是任意大小。

例子：

我的外部列表大小是：4

清单内容

 1. list(0) a,b,c            &nbsp; &nbsp; &nbsp; &nbsp; size:3

 2. list(1) d,b,f,m          &nbsp; &nbsp; &nbsp; size:4

 3. list(2) x,a              &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  size:2

 4. list(3) b,e,d,m,a        &nbsp; &nbsp; size:5

在这里我的组合将是

adxb

adxe 

adxd (adx) duplicate element will be removed after generating combination

adxm

adxa (adx)  

adab (adb)

adae (ade)

...

...很快

我必须通过从每个列表中选择一个元素来生成组合组合长度最大为 4（外部列表的大小），有时如果我在组合中获得相同的元素，它会缩小

我的组合数量将是每个内部列表中元素数量的乘积。

在上面的示例中，组合的数量将是3x4x2x5=120组合

由于我的列表包含重复的元素，如果我有adab adba ，那么我也会在这里得到重复的组合，那么adba是重复的，因为顺序无关紧要。

问题是我使用简单的方法来生成组合，如果我的外部列表大小增加并且我的内部列表包含更多元素，我最终会生成数百万的组合，但只有 1000 或 2000 将是唯一的其余所有重复项。

是否有任何算法方法可以仅生成唯一组合而不是生成所有组合？

4

2 回答 2

1

1：这是作业吗？
2：您预计最多使用多少个列表？

基本上......不会有某种神奇的方式来做到这一点......你将不得不检查你正在构建的字符串是否已经包含你正在考虑添加的字母，这就是你想优化——检查你的字符串是否已经包含一个字母。

如果你这样做是为了家庭作业，我认为你可以使用 String.contains('a') || String.contains('A') 查看字符串是否已经包含某个字母（在这种情况下为'a'）。我会把剩下的留给你。请注意，这是一个 O(n^2) 操作。

如果您这样做是为了更...工业...应用程序，那么我看到了另一种选择。

如果您将拥有大量字符串列表，那么您可能希望使用 TreeSet 来存储您已经使用过的字符列表。例如，在遍历第一个列表（a，b，c）后，您将查看“已用字符”的 TreeSet 是否包含“a”，如果没有，则将“a”添加到您的字符串构建并将“a”添加到已使用字符的 TreeSet 中。然后您将转到第二个列表，查看您的 TreeSet 是否包含字母 d，依此类推。总的来说，这将是一个 o(n*log(n)) 函数。

使用 TreeSet 存储“已使用”字符列表的好处是，添加和检查字符需要 o(log(n))，而不是使用 String 检查字符串中的字符需要 o(n)。包含（“一个”）。（您甚至可以在添加/检查之前将全部转换为小写。）

使用 TreeSet 的不利之处在于，仅实例化 TreeSet 会产生适量的开销，如果您只使用字符串列表的小列表，则可能不值得。

问题：为什么你有一个字符串列表，而不是一个字符列表？似乎字符列表的列表会更合适。

如果你不熟悉我所说的 o(n^2)、o(log(n)) 或 o(n) 的含义，那么 o(whatever) 只是一个表示函数运行时间如何扩展的近似符号传递给该函数的参数数量。
- 例如，如果您运行一个带有 4 个参数的 o(n^2) 函数，它将花费 4^2 == 16 时间（其中“时间”是任意时间单位）。如果使用 8 个参数运行它，则需要 8^2 == 64 次。随着输入大小的增加，它呈二次方增加。
- 例如，如果您运行一个带有 4 个参数的 o(n) 函数，它将执行 4 次。如果你运行一个带有 8 个参数的 o(n) 函数，它将花费 8 时间。
- 例如，如果你运行一个带有 4 个参数的 o(log(n)) 函数，它将花费 2 次。如果你运行一个带有 8 个参数的 o(log(n)) 函数，它将花费 3 时间。（假设日志是以二为底的。

希望你明白了——关键是 o(n^2)、o(n*log(n))、o(n) 和 o(log(n)) 之间的差异很小，数字很小，但是，一旦您开始获取大小为 100 或更大的列表，这将非常重要—— o(n^2) 将花费 10,000 时间，而 o(n*log(n)) 将花费大约 670 时间——也就是说，只有 100 个列表，它会快 15 倍。在 1,000 个列表中，它将快 100 倍。

于 2013-06-03T07:01:44.560 回答
0

我完全出局了。问题是NP难的。建议您找到一种不同的方式来做任何您想做的事情。

编辑：只需重新阅读您的原始帖子。好像你在我昨晚阅读后编辑了它......我现在看到你不是在要求下面的算法，而是为了别的东西。=/ 会考虑它，但可能不会想出任何东西。

public static void main(String[] args) {

    long runningTime = 0;
    int numTrials = 1;

    for( int i = 0; i < numTrials; i++ )
    {
        List<List<String>> theLists = UniqueStringTest.makeListOfLists(12, 5);

        long startTime = System.currentTimeMillis();
        RecursiveAnalyzer ra = new RecursiveAnalyzer( theLists );
        ra.run();
        runningTime += ( System.currentTimeMillis() - startTime );

    }

    System.out.println( "Finished " + numTrials + " trials in " + 
                        runningTime + " milliseconds." );

}

public static class RecursiveAnalyzer implements Runnable
{

    private List<List<String>> theLists;
    private Stack<String> buildingString;
    private TreeSet<String> usedChars;

    public RecursiveAnalyzer( List<List<String>> newTheLists )
    {
        this.theLists = newTheLists;
    }

    public void run()
    {
        this.usedChars = new TreeSet<>();
        this.buildingString = new Stack<>();

        recursiveAnalysisHelper( 0 );
    }

    protected void recursiveAnalysisHelper( int currentDepth )
    {
        List<String> currentList = this.theLists.get( currentDepth );
        boolean haveOneOnStack = false;

        //Iterate over each character in list number currentDepth
        for( int i = 0; i < currentList.size(); i++ )
        {
            if ( this.usedChars.contains( currentList.get(i) ) == false )
            {
                this.usedChars.add( currentList.get(i) );
                this.buildingString.push( currentList.get(i) );
                haveOneOnStack = true;
            }
            else
            {
                haveOneOnStack = false;
            }

            if ( (currentDepth+1) < this.theLists.size() )
            {
                recursiveAnalysisHelper( currentDepth+1 );
            }
            else
            {
                String answer = "";
                for( String s : this.buildingString )
                {
                    answer += s;
                }
                //System.out.println(answer);
            }

            if( haveOneOnStack == true )
            {
                this.buildingString.pop();
                this.usedChars.remove( currentList.get(i) );
            }

        }

    }
}

public static List<List<String>> makeListOfLists( int numLists, int numChars )
{
    List<List<String>> answer = new ArrayList<>();
    Random rand = new Random();
    if ( numChars > 25 )
    {
        numChars = 25;
    }

    for( int i = 0; i < numLists; i++ )
    {
        List<String> anInnerList = new ArrayList<>();
        for( int j = 0; j < numChars; )
        {
            //Makes a lowercase letter
            String aChar = Character.toString((char)(rand.nextInt(26)+97));
            if ( anInnerList.contains( aChar ) == false )
            {
                anInnerList.add( aChar );
                j++;
            }
        }
        answer.add(anInnerList);
    }

    return answer;
}
于 2013-06-04T02:59:42.733 回答