NON CHIEDI AL CODICE DI RISPONDERE A QUESTA SPECIFICA DOMANDA, CHIEDENDO COME APPROCCIO AL PROBLEMA IN GENERALE
c'è una domanda sui combattimenti di codice che richiede di trovare tutte le somme uniche di due matrici, una dimensione, l'altra quantità.
Sto usando un prodotto cartesiano per determinare tutte le possibili permutazioni. Questo sembra essere troppo sovraccarico. qualcuno ha commentato sul sito che qualcuno è stato in grado di farlo in ONE for loop.
Sto cercando una guida su come attaccare il problema da una CPU anziché dall'approccio alla memoria.
int possibleSums(int[] coins, int[] quantity) {
var bitmaps = Enumerable.Range(1, Convert
.ToInt32(new string('1', coins.Length), 2))
.Select(bm => Convert.ToString(bm, 2).PadLeft(coins.Length,'0'));
var sums = coins
.Select((c, i) => new {
Index = i,
Coin = c,
Quantity = quantity[i]
})
.Select(cqi => new {
cqi.Coin,
cqi.Index,
cqi.Quantity,
CoinSums = Enumerable.Range(1, cqi.Quantity)
.Select(s => s * cqi.Coin)
});
var distinctSums = new HashSet<int>();
foreach (var map in bitmaps)
{
var coinsUsed = new List<IEnumerable<int>>();
for (var bitpos = 0; bitpos < map.Length; bitpos++)
{
if (map[bitpos] == '1')
{
coinsUsed.Add(sums.First(s => s.Index == bitpos).CoinSums);
}
}
var coinSums =
CartesianProduct(coinsUsed).Select(x => x.Sum());
foreach (var sum in coinSums)
{
if (!distinctSums.Contains(sum))
distinctSums.Add(sum);
}
}
return distinctSums.Count();
}
IEnumerable<IEnumerable<T>> CartesianProduct<T>( IEnumerable<IEnumerable<T>> sequences)
{
IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>()};
return sequences.Aggregate(
emptyProduct,
(accumulator, sequence) =>
from accseq in accumulator
from item in sequence
select accseq.Concat(new[] {item})
);
}