Losowanie kombinacji liczb z dwóch tablic bez powtórzeń

0

Witam, wszystkich w programie muszę napisać losowanie z dwóch zbiorów (nie muszą to być koniecznie tablice) kombinacji liczb n razy z tym ,że kombinacje nie mogą się powtórzyć i niestety nie wiem jak najlepiej do tego podejść. Na myśl nasuwają mi się dwie oczywiste opcje:

-Stworzenie tablicy z wszystkich kombinacji (permutacja) i losowanie z niej
-Losowanie z dwóch tablic i sprawdzenie czy nie ma już takiego wyniku

Ale obie opcje mi się nie podobają. Przy pierwszej ze względu na dużą ilość kombinacji (tablice do paru tysięcy liczb) przy drugiej to ilość kombinacji do wylosowania ,która może dochodzić nawet do 1000. Dlatego wpadłem na trzeci pomysł, tylko sam nie wiem czy on będzie dobry sposobem.

-Stworzenie dwuwymiarowej listy za pomocą addrange, z której po wylosowaniu będę wyjmował obie kombinacje np 3/2 i 2/3.

Jakie rozwiązanie jest najbardziej optymalne dla tego problemu? Dodam, iż oczywiście szukałem odpowiedzi w internecie.

Z góry dziękuje za pomoc.

0

Jak masz np. 20 elementów tablicy tab [20] to randem wylosuj liczbę od 0 do 19. Podstaw tab[rand] i będziesz miał liczbę losową. Jak nie chcesz powtórzeń to podstaw w miejsce wylosowanego indeksu ostatni np tab[rand] = tab[19] i przy następnym losowaniu losuj od 0 do 18. Sorry że chaotycznie ale siedzę na kiblu i pisze z telefonu

1

Kod opisałem, o to chodziło?

/// <summary>
    /// Klasa do losowania dwóch liczb ze zbioru x,y niepowtarzających się
    /// </summary>
    public class MyRand
    {
        /// <summary>
        /// Tworzy nowe wystąpienie instancji obiektu <see cref="MyRand"/>
        /// </summary>
        /// <param name="Array1">Liczby zbioru 1. Ilość elementów musi być identyczna jak w zbiorze <see cref="Array2"/></param>
        /// <param name="Array2">Liczby zbioru 2. Ilość elementów musi być identyczna jak w zbiorze <see cref="Array1"/></param>
        /// <exception cref="ArgumentException"/>
        public MyRand(IEnumerable<int> Array1, IEnumerable<int> Array2)
        {
            if (Array1 == null || Array1.Count() == 0 || Array2 == null || Array2.Count() == 0)
                throw new ArgumentException("Przynajmniej jeden ze zbiorów jest pusty lub ilość elementów w zbiorach nie jest identyczna");
            array1 = Array1.ToList();
            array2 = Array2.ToList();
        }
        /// <summary>
        /// Pozostałe liczby w zbiorze nr 1;
        /// </summary>
        private List<int> array1;
        /// <summary>
        /// Pozostałe liczby w zbiorze nr 2
        /// </summary>
        private List<int> array2;
        /// <summary>
        /// Losuje liczbę ze zbioru <see cref="MyRand.array1"/> (Key) oraz ze zbioru <see cref="MyRand.array2"/> (Value)
        /// </summary>
        /// <returns></returns>
        /// <exception cref="InvalidOperationException"
        public KeyValuePair<int, int> GetNext()
        {
            if (array1.Count() == 0 || array2.Count() == 0)
                throw new InvalidOperationException("Skończyły się liczby w zbiorach");
            Random random1 = new Random();
            int index1 = random1.Next(0, array1.Count());
            int index2 = random1.Next(0, array2.Count());
            KeyValuePair<int, int> ret = new KeyValuePair<int, int>(array1[index1], array2[index2]);
            return ret;
        }
        /// <summary>
        /// Losuje liczbę ze zbioru <see cref="MyRand.array1"/> (Key) oraz ze zbioru <see cref="MyRand.array2"/> (Value). Na koniec usuwa wylosowane liczby ze zbioru
        /// </summary>
        /// <returns></returns>
        /// <exception cref="InvalidOperationException"
        public KeyValuePair<int, int> GetNextAndDelete()
        {
            if (array1.Count() == 0 || array2.Count() == 0)
                throw new InvalidOperationException("Skończyły się liczby w zbiorach");
            Random random1 = new Random();
            int index1 = random1.Next(0, array1.Count());
            int index2 = random1.Next(0, array2.Count());
            KeyValuePair<int, int> ret = new KeyValuePair<int, int>(array1[index1], array2[index2]);
            array1.RemoveAt(index1);
            array2.RemoveAt(index2);
            return ret;
        }
        /// <summary>
        /// Losuje i usuwa wszystkie elementy ze zbiorów
        /// </summary>
        public IEnumerable<KeyValuePair<int, int>> RandAllElements
        {
            get
            {
                while(array1.Count > 0)
                {
                    yield return GetNextAndDelete();
                }
            }
        }
    }

Przykład użycia:

MyRand myRand = new MyRand(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });

        private void Button_Click(object sender, RoutedEventArgs e)
        {
            var v = myRand.GetNextAndDelete();
            hList.Items.Add("Zbiór 1: " + v.Key + ", Zbiór 2: " + v.Value);
        }

Przykład użycia 2:

MyRand myRand = new MyRand(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });

        private void Button_Click(object sender, RoutedEventArgs e)
        {
            foreach(var v in myRand.RandAllElements)
                hList.Items.Add("Zbiór 1: " + v.Key + ", Zbiór 2: " + v.Value);
        }
2

Tak bym to zrobił:

using System;
using System.Collections.Generic;

public class Combinator
{
    private static readonly Random Random = new Random();
    private readonly IList<int> firstList;
    private readonly IList<int> secondList;
    private readonly HashSet<long> drawnCombinations = new HashSet<long>();

    public Combinator(IList<int> firstList, IList<int> secondList)
    {
        this.firstList = firstList;
        this.secondList = secondList;
    }
  
    public IEnumerable<(int, int)> GetNext(int count)
    {
        while(count-- > 0)
        {
            yield return GetNext();
        }       
    }

    private (int, int) GetNext()
    {
        int tryCount = 0;

        while (++tryCount < 666)
        {
            int firstListIndex = Random.Next(0, firstList.Count);
            int secondListIndex = Random.Next(0, secondList.Count);
            var combination = (firstList[firstListIndex], secondList[secondListIndex]);
            long hash1 = ((long)combination.Item1 << 32) | (long)combination.Item2;
            long hash2 = ((long)combination.Item2 << 32) | (long)combination.Item1;
            if (!drawnCombinations.Contains(hash1))
            {
                drawnCombinations.Add(hash1);
                drawnCombinations.Add(hash2);
                return combination;
            }
        }

        throw new InvalidOperationException("I am out of luck :(");
    }
}

class TestClass
{
    static void Main(string[] args)
    {
        var combinator = new Combinator(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });

        foreach(var combination in combinator.GetNext(20))
        {
            Console.WriteLine($"{{{combination.Item1}, {combination.Item2}}}");
        }
    }
}
0

@neves: Czy mógłbyś wytłumaczyć mi łopatologicznie ?

long hash1 = ((long)combination.Item1 << 32) | (long)combination.Item2;
 long hash2 = ((long)combination.Item2 << 32) | (long)combination.Item1;

Nie mogę tego zrozumieć :(

0

ten kod łączy dwa 32bitowe inty w jeden 64bitowy long.
13 = 0000 0000 0000 0000 0000 0000 0000 1101 (32)
7 = 0000 0000 0000 0000 0000 0000 0000 0111 (32)
13 + 7 = 0000 0000 0000 0000 0000 0000 0000 1101 0000 0000 0000 0000 0000 0000 0000 0111 (64)
7 + 13 = 0000 0000 0000 0000 0000 0000 0000 0111 0000 0000 0000 0000 0000 0000 0000 1101 (64)

0

HashSet<T> i dodawaj elementy, jeżeli 2,3 i 3,2 jest tym samym dla Ciebie to zrób sobie jakąś strukturę, która je ustawia rosnąco i implementuje IEqualityComparer<T>

Na początku warto sprawdzić czy jest już struktura, która zawiera odpowiednią funkcjonalność, chyba, że lubisz wynajdować koło na nowo

1 użytkowników online, w tym zalogowanych: 0, gości: 1