Problema de listas

gistfile1.md

• Há dois tipos de itens: A e B
• Os items do tipo B podem ser convertidos para A' e A"
• Dado uma lista com itens A e B (ordem dos itens não é relevante), é necessário gerar o maior número possível de listas-alvo somente com A, A' e A" (substituindo o itens B em A' ou A") dentro do tempo limite t
• O número de possibilidades únicas é n² on n é o número de itens B
• Os itens A não precisam ser modificados, podendo ser reutilizados como lista-alvo inicial (concatenado-se as substituições de B)

Dado a lista inicial (pode ter tamanho arbitrário):

[A, A, B, A, B]

Estas são as listas-alvo:

[A, A, A', A, A']
[A, A, A", A, A']
[A, A, A", A, A"]

As listas-alvo são ordenadas posteriomente, portanto a ordem dos itens não é relevante, nem mesmo gerar cada possibilidade. Apenas as listas-alvo únicas devem estar no resultado. Esse é o motivo da opção [A, A, A', A, A"] não estar presente no exemplo acima.

Este código aqui (C#), retorna todas as combinações possíveis (Sem repetir elementos) de elementos de uma lista.

Exemplo:

c=>[A,B,C] = [[A],[B],[C],[A,B],[A,C],[B,C],[A,B,C]]

    public static List<List<T>> RetornaCombinacoes<T>(List<T> lista)
    {
        var contador = (int)Math.Pow(2, lista.Count) - 1;
        var resultado = new List<List<T>>();
        for (int i = 1; i < contador + 1; i++)
        {
            resultado.Add(new List<T>());
            for (int j = 0; j < lista.Count; j++)
            {
                if ((i >> j) % 2 != 0)
                {
                    resultado.Last().Add(lista[j]);
                }
            }
        }
        return resultado;
    }

• Realizar combinações dos membros de A, três à três (filtrando o resultado deste método buscando listas de tamanho 3);
• Realizar combinações dos membros de B, dois à dois (filtrando o resultado deste método buscando listas de tamanho 2);
• Para cada conjunto de A
  • Para cada conjunto de B
    • Criar uma lista de resultados com o conjunto A
    • Adicionar membros de B, na 3a e 5a posições;
    • Adicionar esta lista em uma lista de resultados.