长度有限的C#列表排列 [英] c# list permutations with limited length

问题描述

我有一个优惠"列表，我想从中创建链接长度有限的链"(例如排列).

I have a list of Offers, from which I want to create "chains" (e.g. permutations) with limited chain lengths.

我已经使用Kw.Combinatorics 项目. 但是，默认行为会在列表计数的长度上创建排列.我不确定如何将链长度限制为"n".

I've gotten as far as creating the permutations using the Kw.Combinatorics project. However, the default behavior creates permutations in the length of the list count. I'm not sure how to limit the chain lengths to 'n'.

这是我当前的代码:

    private static List<List<Offers>> GetPerms(List<Offers> list, int chainLength)
    {
        List<List<Offers>> response = new List<List<Offers>>();
        foreach (var row in new Permutation(list.Count).GetRows())
        {
            List<Offers> innerList = new List<Offers>();
            foreach (var mix in Permutation.Permute(row, list))
            {
                innerList.Add(mix);

            }
            response.Add(innerList);
            innerList = new List<Offers>();
        }
        return response;
    }

实现者:

List<List<AdServer.Offers>> lst = GetPerms(offers, 2);

如果有人可以提供更好的解决方案，我不会被KWCombinatorics所困.

I'm not locked in KWCombinatorics if someone has a better solution to offer.

推荐答案

您不是要查找排列，而是要查找变异.这是一种可能的算法.对于可能会返回很多元素的函数，我更喜欢使用迭代器方法.这样，呼叫者可以决定他是否真的需要所有元素:

You're not looking for a permutation, but for a variation. Here is a possible algorithm. I prefer iterator methods for functions that can potentially return very many elements. This way, the caller can decide if he really needs all elements:

IEnumerable<IList<T>> GetVariations<T>(IList<T> offers, int length)
{
    var startIndices = new int[length];
    var variationElements = new HashSet<T>(); //for duplicate detection

    while (startIndices[0] < offers.Count)
    {                
        var variation = new List<T>(length);
        var valid = true;
        for (int i = 0; i < length; ++i)
        {
            var element = offers[startIndices[i]];
            if (variationElements.Contains(element))
            {
                valid = false;
                break;
            }
            variation.Add(element);
            variationElements.Add(element);
        }
        if (valid)
            yield return variation;

        //Count up the indices
        startIndices[length - 1]++;
        for (int i = length - 1; i > 0; --i)
        {
            if (startIndices[i] >= offers.Count)
            {
                startIndices[i] = 0;
                startIndices[i - 1]++;
            }
            else
                break;
        }
        variationElements.Clear();
    }
}

此算法的想法是使用以offers.Count为基数的数字.对于三个报价，所有数字均在0-2范围内.然后，我们基本上会逐步增加此数字，并返回位于指定索引处的报价.如果要允许重复，可以删除支票和HashSet<T>.

The idea for this algorithm is to use a number in offers.Count base. For three offers, all digits are in the range 0-2. We then basically increment this number step by step and return the offers that reside at the specified indices. If you want to allow duplicates, you can remove the check and the HashSet<T>.

这是一个优化的变体，可以在索引级别进行重复检查.在我的测试中，它比以前的版本要快得多:

Here is an optimized variant that does the duplicate check on the index level. In my tests it is a lot faster than the previous variant:

IEnumerable<IList<T>> GetVariations<T>(IList<T> offers, int length)
{
    var startIndices = new int[length];
    for (int i = 0; i < length; ++i)
        startIndices[i] = i;

    var indices = new HashSet<int>(); // for duplicate check

    while (startIndices[0] < offers.Count)
    {
        var variation = new List<T>(length);
        for (int i = 0; i < length; ++i)
        {
            variation.Add(offers[startIndices[i]]);
        }
        yield return variation;

        //Count up the indices
        AddOne(startIndices, length - 1, offers.Count - 1);

        //duplicate check                
        var check = true;
        while (check)
        {
            indices.Clear();                    
            for (int i = 0; i <= length; ++i)
            {
                if (i == length)
                {
                    check = false;
                    break;
                }
                if (indices.Contains(startIndices[i]))
                {
                    var unchangedUpTo = AddOne(startIndices, i, offers.Count - 1);
                    indices.Clear();
                    for (int j = 0; j <= unchangedUpTo; ++j )
                    {
                        indices.Add(startIndices[j]);
                    }
                    int nextIndex = 0;
                    for(int j = unchangedUpTo + 1; j < length; ++j)
                    {
                        while (indices.Contains(nextIndex))
                            nextIndex++;
                        startIndices[j] = nextIndex++;
                    }
                    break;
                }

                indices.Add(startIndices[i]);
            }
        }
    }
}

int AddOne(int[] indices, int position, int maxElement)
{
    //returns the index of the last element that has not been changed

    indices[position]++;
    for (int i = position; i > 0; --i)
    {
        if (indices[i] > maxElement)
        {
            indices[i] = 0;
            indices[i - 1]++;
        }
        else
            return i;
    }
    return 0;
}

这篇关于长度有限的C#列表排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！