Mise en œuvre du modèle de sous-ensemble

Question

J'essaie d'écrire une implémentation en C# du modèle Subsets lu ici 14 modèles pour répondre à toutes les questions d'entretien sur le codage :

Cela semble évident mais me perturbe. Mes recherches m'ont appris qu'il fallait l'implémenter via des Jagged Arrays (et non des Multidimensional Arrays). J'ai commencé :

int[] input = { 1, 5, 3 };
int[][] set = new int[4][];
// ...

Quelqu'un pourrait-il nous aider pour les étapes 2, 3 et 4 ?

Answer 1

Les instructions fournies semblent se prêter davantage à une c++ qu'une C# le style. Je pense qu'il existe de meilleurs moyens que la construction manuelle de tableaux pour obtenir une liste de sous-ensembles en C# . Cela dit, voici comment je procéderais pour mettre en œuvre les instructions telles qu'elles sont rédigées.

---

Pour éviter d'avoir à augmenter de façon répétée le tableau de sous-ensembles, nous devons calculer sa longueur avant de l'allouer.

Assumer n dans l'entrée, nous pouvons déterminer le nombre de sous-ensembles possibles en les additionnant :

• Tous les sous-ensembles avec 0 les éléments (l'ensemble vide)
• Tous les sous-ensembles avec 1 élément
• Tous les sous-ensembles avec 2 éléments
• ...
• Tous les sous-ensembles avec n-1 éléments
• Tous les sous-ensembles avec n les éléments (l'ensemble lui-même)

Mathématiquement, il s'agit de la récapitulation de la coefficient binomial . Nous prenons la somme de 0 à n de n choisir k qui s'évalue à 2^n .

Le tableau en dents de scie devrait alors contenir 2^n des tableaux dont la longueur varie de 0 à n .

var input = new int[] { 1, 3, 5 };

var numberOfSubsets = (int)Math.Pow(2, input.Length);

var subsets = new int[numberOfSubsets][];

---

Comme l'indiquent les instructions de votre article, nous commençons par ajouter l'ensemble vide à notre liste de sous-ensembles.

int nextEmptyIndex = 0;

subsets[nextEmptyIndex++] = new int[0];

Ensuite, pour chaque élément de notre entrée, nous enregistrons la fin des sous-ensembles existants (afin de ne pas nous retrouver dans une boucle infinie à poursuivre les nouveaux sous-ensembles que nous ajouterons) et nous ajoutons le(s) nouveau(x) sous-ensemble(s).

foreach (int element in input)
{
    int stopIndex = nextEmptyIndex - 1;

    // Build a new subset by adding the new element
    // to the end of each existing subset.
    for (int i = 0; i <= stopIndex; i++)
    {
        int newSubsetLength = subsets[i].Length + 1;
        int newSubsetIndex = nextEmptyIndex++;

        // Allocate the new subset array.
        subsets[newSubsetIndex] = new int[newSubsetLength];

        // Copy the elements from the existing subset.
        Array.Copy(subsets[i], subsets[newSubsetIndex], subsets[i].Length);

        // Add the new element at the end of the new subset.
        subsets[newSubsetIndex][newSubsetLength - 1] = element;
    }

}

---

Avec un peu d'enregistrement à la fin, nous pouvons voir notre résultat :

for (int i = 0; i < subsets.Length; i++)
{
    Console.WriteLine($"subsets[{ i }] = { string.Join(", ", subsets[i]) }");
}

subsets[0] = 
subsets[1] = 1
subsets[2] = 3
subsets[3] = 1, 3
subsets[4] = 5
subsets[5] = 1, 5
subsets[6] = 3, 5
subsets[7] = 1, 3, 5

---

Essayez-le !

Answer 2

Ce que je trouve le plus facile, c'est de traduire le problème d'une mot en un problème plus logique.

Commencer par un ensemble vide : [[]]

L'astuce consiste à créer un ensemble vide dans ce problème mais immédiatement vous montre un ensemble qui contient un élément.

Si nous décomposons cela en tableaux à la place (parce que je trouve personnellement que c'est plus intuitif), nous pouvons le traduire par :

Commencez par un tableau de tableaux, dont le premier élément est un tableau vide. (au lieu de null )

En résumé

int[][] result = new int[]{ new int[0] };

Maintenant que nous avons un point de départ, nous pouvons commencer à traduire les autres parties du problème.

Ajoutez le premier numéro (1) à tous les sous-ensembles existants pour créer des sous-ensembles : [[],[1]]
Ajouter le deuxième chiffre (5) à tous les sous-ensembles existants ...
Ajouter le troisième chiffre (3) à tous les sous-ensembles existants ...

Il y a beaucoup d'informations ici. Traduisons-en les différentes parties

Ajouter le 1er numéro ...
Ajouter le 2e numéro ...
Ajouter le nième nombre ...

La répétition de ces instructions et le fait que chaque nombre 1, 5, 3 correspond à notre ensemble initial de {1, 5, 3} nous indique que nous devrions utiliser un boucle d'une manière ou d'une autre pour construire notre résultat.

for(int i = 0; i < set.Length; i++)
{
    int number = set[i];

    // add subsets some how
}

Ajouter le numéro à tous les pour créer des sous-ensembles : [[],[1]

Quelques points méritent d'être soulignés. Remarquez qu'ils ont utilisé le mot Ajouter mais donnez un exemple où le numéro n'a pas été ajouté à l'un des sous-ensembles existants. [[]] s'est transformé en [[],[1]] . Pourquoi l'un d'entre eux reste-t-il vide si nous avons ajouté 1 à chacun d'entre eux ?

La raison en est que lorsque nous créons les nouveaux sous-ensembles et toutes leurs variations, nous voulons conserver les anciens. Ainsi, nous faire ajouter le 1 à [] (le premier élément) mais nous faisons un copie de [] d'abord. Ainsi, lorsque nous ajouterons 1 à cette copie, nous disposons toujours de l'original [] et maintenant un tout nouveau [1] on peut alors combiner les créer [[],[1]] .

Grâce à ces indices, nous pouvons déchiffrer que Ajouter le numéro à tous les sous-ensembles existants signifie en fait fait des copies de tous les sous-ensembles existants, ajoute le nombre à chacune des copies, puis ajoute ces copies à la fin du tableau de résultats .

int[][] result = new int[]{ new int[0] };

int[] copy = result[0];

copy.Append(1); // pseudo code

result.Append(copy); // pseudo code

// result: [[],[1]]

Rassemblons toutes ces pièces et trouvons la solution finale, du moins nous l'espérons !

Voici un exemple que j'ai mis au point et qui fonctionne (du moins selon les données de votre exemple).

object[] set = { 1, 5, 3 };

// [null]
object[][] result = Array.Empty<object[]>();

// add a [] to the [null] creating [[]]
Append(ref result, Array.Empty<object>());

// create a method so we can add things to the end of an array
void Append<T>(ref T[] array, T SubArrayToAdd)
{
    int size = array.Length;

    Array.Resize(ref array, size + 1);

    array[size] = SubArrayToAdd;
}

// create a method that goes through all the existing subsets and copies them, adds the item, and adds those copies to the result array
void AddSubsets(object item)
{
    // store the length of the result because if we don't we will infinitely expand(because we resize the array)
    int currentLength = result.Length;

    for (int i = 0; i < currentLength; i++)
    {
        // copy the array so we don't change the original
        object[] previousItemArray = result[i];  // []

        // add the item to it
        Append(ref previousItemArray, item);     // [1]

        // add that copy to the results
        Append(ref result, previousItemArray);   // [[]] -> [[],[1]]
    }
}

// Loop over the set and add the subsets to the result
for (int i = 0; i < set.Length; i++)
{
    object item = set[i];

    AddSubsets(item);
}