Problemas de contagem – uma implementação em C#

No texto anterior apresentei uma série e problemas de contagem dos arranjos de um conjunto de bolas num conjunto de caixas, obedecendo a determinadas regras. No entanto, os processos de contagem não implicam a construção de todas as referências. Por exemplo, um conjunto de três bolas diferentes numeradas de 1 a 3 podem ser arranjadas de 6 maneiras em três caixas de modo que cada caixa contenha apenas uma bola. Representamos por (1,3,2) como sendo a configuração associada à bola 1 na primeira caixa, à bola 3 na segunda e à bola 2 na terceira. A enumeração para este caso será

\left\lbrace (1,2,3), (1,3,2), (2,1,3), (2,3,1),(3,1,2), (3,2,1) \right\rbrace

Quando os problemas são desta ordem de grandeza, a enumeração manual torna-se simples. Quando está envolvido um número maior de bolas e caixas, o caso muda de figura com extrema facilidade. Com isto em mente, programei em C# um iterador que pode ser configurado para listar todos os arranjos associados aos problemas previamente citados e até mesmo ser estendido a outros problemas de natureza mais complexa. Assenta na classe Affector cujo código se segue:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CodeTests.Collections
{
public delegate bool AffectationVerifier(int[] previousConsideredSolutions, int currentInsertionValue);

public class Affector : IEnumerable<int[]>
{
private int[] indices;
private int[][] affectationIndices;
private AffectationVerifier solutionVerifier;

public Affector(int[] indices, int[][] affectationIndices, AffectationVerifier verifier)
{
if (indices == null || affectationIndices == null)
{
throw new ArgumentException("Indices and affectation indices must not be null");
}
if (indices.Length == 0)
{
throw new ArgumentException("There are no indices to be affected.");
}
if (affectationIndices.GetLength(0) != indices.Length)
{
throw new ArgumentException("First dimension of affectation indices must have the same quantity of elements as indices to be affected.");
}
this.indices = indices;
this.affectationIndices = affectationIndices;
this.solutionVerifier = verifier;
}

#region IEnumerable<int[]> Members

public IEnumerator<int[]> GetEnumerator()
{
return new AffectorEnumerator(this.indices, this.affectationIndices, this.solutionVerifier);
}

#endregion

#region IEnumerable Members

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}

#endregion
}

/// <summary>
/// General affectation enumerator.
/// </summary>
public class AffectorEnumerator : IEnumerator<int[]>
{
private int[] indices;
private int[][] affectationIndices;
private AffectationVerifier solutionVerifier;
private bool isBeforeStart = true;
private bool isAfterEnd = false;
private int[] currentAffectationIndices;
int currentPointer = 0;
int state = 0;

public AffectorEnumerator(int[] indices, int[][] affectationIndices, AffectationVerifier verifier)
{
this.indices = indices;
this.affectationIndices = affectationIndices;
this.solutionVerifier = verifier;
this.currentAffectationIndices = new int[indices.Length];
}

#region IEnumerator<int[]> Members

public int[] Current
{
get { return this.GetCurrent(); }
}

#endregion

#region IDisposable Members

public void Dispose()
{
this.indices = null;
this.affectationIndices = null;
this.solutionVerifier = null;
this.currentAffectationIndices = null;
return;
}

#endregion

#region IEnumerator Members

object System.Collections.IEnumerator.Current
{
get { return this.Current; }
}

public bool MoveNext()
{
if (this.isBeforeStart)
{
this.isBeforeStart = false;
return this.AdvanceState();
}
else
{
if (this.AdvanceState())
{
return true;
}
else
{
return false;
}
}
}

public void Reset()
{
this.isAfterEnd = false;
this.isBeforeStart = true;
this.currentPointer = 0;
this.state = 0;
}

#endregion

private bool AdvanceState()
{
bool go = true;
while (go)
{
if (this.state == 0)
{
if (this.currentPointer == this.indices.Length)
{
if (this.currentPointer == 0)
{
this.isAfterEnd = true;
return false;
}
this.state = 1;
go = false;
}
else if (this.currentAffectationIndices[this.currentPointer] == this.affectationIndices[this.currentPointer].Length)
{
this.state = 1;
}
else if (this.VerifySolution(this.GetArgumentIndices(), this.affectationIndices[this.currentPointer][this.currentAffectationIndices[this.currentPointer]]))
{
++this.currentPointer;
if (this.currentPointer < this.currentAffectationIndices.Length)
{
this.currentAffectationIndices[this.currentPointer] = 0;
}
}
else
{
++this.currentAffectationIndices[this.currentPointer];
}
}
else if (this.state == 1)
{
--this.currentPointer;
if (this.currentPointer < 0)
{
this.isAfterEnd = true;
return false;
}
++this.currentAffectationIndices[this.currentPointer];
if (this.currentAffectationIndices[this.currentPointer] != this.affectationIndices[this.currentPointer].Length)
{
this.state = 0;
}
}
}
return true;
}

private int[] GetCurrent()
{
if (isBeforeStart)
{
throw new Exception("Enumerator is in \"IsBeforeStart\" status.");
}
int[] result = new int[this.currentAffectationIndices.Length];
for (int i = 0; i < this.currentAffectationIndices.Length; ++i)
{
result[i] = this.affectationIndices[i][this.currentAffectationIndices[i]];
}
return result;
}</p>
<p style="text-align: justify;"><br style="text-align: justify;" />        /// <summary>
/// Gets the integer list argument to be passed to verifier function.
/// </summary>
/// <returns></returns>
private int[] GetArgumentIndices()
{
int[] result = new int[this.currentPointer];
for (int i = 0; i < this.currentPointer; ++i)
{
result[i] = this.affectationIndices[i][this.currentAffectationIndices[i]];
}
return result;
}

private bool VerifySolution(int[] previousElements, int insertedElement)
{
if (this.solutionVerifier == null)
{
return true;
}
return this.solutionVerifier.Invoke(previousElements, insertedElement);
}
}
}

O construtor da classe recebe três parâmetros. O primeiro parâmetro corresponde à numeração das bolas, o qual é um simples vector. O segundo parâmetro é um vector de vectores e contém, para cada entrada da primeira dimensão, todos os números das caixas onde a bola pode ser atribuída. Obviamente, a primeira dimensão deste vector terá de ter tantos elementos quantas as bolas. O terceiro parâmetro consiste num apontador para a função que permite descartar configurações inválidas.

O iterador começa por colocar a primeira bola na primeira caixa válida e chama a função para verificar se o pode fazer. De seguida, coloca a segunda bola na sua primeira caixa válida e chama a função para verificar a validade dessa atribuição. Suponhamos que atribuiu a primeira bola à caixa 1 e vai tentar atribuir a segunda bola à caixa 1. Se as caixas não podem conter mais do que uma bola, a função retornará um valor falso e a iterador atribuirá a segunda bola à caixa 2. A implementação da função é deixada ao cargo do utilizador. Obviamente, o iterador terá de passar, como argumentos, um vector com os números das caixas às quais as bolas anteriores foram atribuídas e o número da caixa à qual a bola corrente se está a tentar atribuir.

A título de exemplo, consideramos três bolas e seis caixas, onde cada bola pode ser atribuída a qualquer caixa. Temos as funções

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CodeTests
{
public class Program
{
static void PrintArray<T>(T[] array)
{
if(array == null)
{
Console.Write("null");
return;
}
Console.Write("[");
if(array.Length > 0)
{
Console.Write(array[0]);
for (int i = 1; i < array.Length; ++i)
{
Console.Write(", ");
Console.Write(array[i]);
}
}
Console.Write("]");
}

static void Main(string[] args)
{
int[] indices = new int[]{ 1, 2, 3 };
int[][] affectionIndices = new int[][] {new int[]{1, 2, 3}, new int[]{3, 4}, new int[]{4, 5}};
Collections.Affector affector = new CodeTests.Collections.Affector(indices,
affectionIndices, new CodeTests.Collections.AffectationVerifier(VerifiySolution));
Console.WriteLine("Affectation values:");
foreach (var v in affector)
{
PrintArray<int>(v);
Console.WriteLine();
}
}
}

Na função main é criado um vector, indices, o qual contém os objectos a afectar. Como o iterador apenas afecta em termos de índices, este vector não precisa de ser inicializado com o número atribuído às bolas (de facto, este parâmetro é supérfluo). O vector affectationIndices recebe o número das caixas nas quais cada bola pode ser colocada. A primeira dimensão deste vector tem três elementos para se coadunar com o número de bolas no vector indices e, a cada índice, corresponde um vector com valores de 1 a 6. A variável v, no ciclo, irá corresponder a um vector cujas entradas são o número da caixa onde a bola está a ser colocada, de acordo com a notação apresentada na introdução. Resta-nos definir a função VerifySolution, a qual permite definir as afectações válidas mediante o problema em questão.

Problema: determinar todos os arranjos possíveis das três bolas nas seis caixas de modo que cada caixa contenha apenas uma bola.

A solução é dada pelo código seguinte:

static bool VerifiySolution(int[] initSol, int appended)
{
foreach (var number in initSol)
{
if (number == appended)
{
return false;
}
}
return true;
}

É fácil de verificar que, se a bola corrente está a ser afectada à caixa appended, então este valor não pode existir no vector initSol que contém as afectações das bolas anteriores.

Problema: determinar todos os arranjos das três bolas nas seis caixas de modo que cada caixa possa conter um número arbitrário de bolas.

Este problema é deveras fácil. De facto, as bolas podem ser colocadas sem quaisquer restrições.

static bool VerifiySolution(int[] initSol, int appended)
{
return true;
}

Problema: colocar as três bolas nas seis caixas supondo que estas são semelhantes e que cada caixa possa conter uma única bola.

Neste problema, as bolas terão ser sempre colocadas na mesma ordem, isto é, se a bola 1 for colocada na terceira caixa, todas as restantes bolas terão de ser colocadas daí em diante.

static bool VerifiySolution(int[] initSol, int appended)
{
if (initSol.Length == 0)
{
return true;
}
if (appended <= initSol[initSol.Length - 1])
{
return false;
}
return true;
}

Problema: construir as combinações nas quais três bolas são atribuídas a seis caixas de modo que a bola no índice 0 seja igual à bola no índice 1 e cada caixa apenas poderá conter uma bola.

A restrição que importa neste problema resume-se a considerar apenas as colocações que mantenham a ordem dos índices correspondentes às bolas semelhantes.

static bool VerifiySolution(int[] initSol, int appended)
{
int[] sameBall = new int[2] { 0, 1 };
bool contains = sameBall.Contains(initSol.Length);
for (int i = 0; i < initSol.Length; ++i)
{
if (sameBall.Contains(i) && contains)
{
if (initSol[i] > appended)
{
return false;
}
}
if (initSol[i] == appended) return false;
}
return true;
}

Problema: determinar todas as combinações de três bolas iguais nas seis caixas de modo que cada caixa possa levar um número arbitrário de bolas.

Trata-se do problema aferente às combinações com repetição. No que respeita ao código, não difere muito do problema das combinações, isto é, aquele em que colocamos as bolas semelhantes onde cada caixa só pode conter uma.

static bool VerifiySolution(int[] initSol, int appended)
{
if (initSol.Length == 0)
{
return true;
}
if (appended < initSol[initSol.Length - 1])
{
return false;
}
return true;
}

A enumeração relativa a outros problemas que possam surgir depende da imaginação e sagacidade de quem a implementa. Apesar dum iterador deste género parecer desprovido de interesse quanto à sua aplicação em produção, posso garantir que tive a necessidade de o aperfeiçoar por motivos profissionais.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Computadores e Internet, Matemática. ligação permanente.

Uma resposta a Problemas de contagem – uma implementação em C#

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s