Check sets contain/match the set of a set in Dart-CodePudding

A sets receipt is a set of sets:

Set dish1 = {'a', 'b'};
Set dish2 = {'c', 'd'};
Set dish3 = {'a', 'b', 'c'};
Set dish4 = {'a', 'b', 'c', 'd'};
Set receipt = {dish1, dish2, dish3, dish4};

I would like to find the logic that can test whether a material belongs to a certain dish of above receipt.

Set material1 = {'a', 'b'}; // return dish1
Set material2 = {'a', 'b', 'c'}; // dish3
Set material3 = {'a', 'b', 'd'}; // null
Set material4 = {'b', 'c', 'a'}; // dish3

material3 {'a', 'b', 'd'} returns null not the dish1 because I'm looking for an exact element match but the order doesn't matter so material4 {'b', 'c', 'a'} can return dish3.

Thank you.

CodePudding user response：

You need a way to compare sets for equality, in order to see whether one set is equal to another. You can use package:collection's SetEquality for that.

That would make the code to look up an set in set of sets:

Set? findDish(Set<Set> receipt, Set dish) {
  for (var receiptDish in receipt) {
    if (const SetEquality().equals(receiptDish, dish)) {
      return receiptDish;
    }
  }
  return null;
}

That's not particularly efficient. Instead you could use a custom hash map to store the receipts, and allow direct lookup by a set:

const setEquality = SetEquality();
Set<Set> receipt = HashSet<Set>(
    equals: setEquality.equals, hashCode: setEquality.hash)
  ..addAll([dish1, dish2, dish3, dish4]);

Then you can directly look up a set in the other set:

Set? material1 = receipt.lookup({'a', 'b'}); // return dish1
Set? material2 = receipt.lookup({'a', 'b', 'c'}); // dish3
Set? material3 = receipt.lookup({'a', 'b', 'd'}); // null
Set? material4 = receipt.lookup({'b', 'c', 'a'}); // dish3

CodePudding user response：

To be able to have dish1, dish2, etc. available for your result, they actually have to be in your program. You can do this with a Map.

void main() {
  var receipt = {
    'dish1': {'a', 'b'},
    'dish2': {'c', 'd'},
    'dish3': {'a', 'b', 'c'},
    'dish4': {'a', 'b', 'c', 'd'},
  };

  var availableIngredients = {'b', 'c', 'a'};

  var dishesWithAvailableIngredients = receipt
    .entries
    .where(
      (entry) => entry.value.containsAll(availableIngredients)
    )
    .map((entry) => entry.key);
    
  print(dishesWithAvailableIngredients);
}

Of course, it might be nice to have some more structured data model in place:

void main() {
  var receipt = new Receipt([
    new Dish(name: 'dish1', ingredients: {'a', 'b'}),
    new Dish(name: 'dish2', ingredients: {'c', 'd'}),
    new Dish(name: 'dish3', ingredients: {'a', 'b', 'c'}),
    new Dish(name: 'dish4', ingredients: {'a', 'b', 'c', 'd'}),
  ]);
  print(receipt.dishesWithIngredients({'b', 'c', 'a'}));
}

class Dish {
  // Might also want to track quantity, but I'm leaving that out
  String name;
  Set<String> ingredients;

  Dish({String name, Set<String> ingredients}) {
    this.name = name;
    this.ingredients = ingredients;
  }

  bool containsAll(Set<String> ingredients) {
    return this.ingredients.containsAll(ingredients);
  }

  String toString() {
    return "Dish(name: ${name}, ingredients: ${ingredients})";
  }
}

class Receipt {
  List<Dish> dishes;

  Receipt(List<Dish> dishes) {
    this.dishes = dishes;
  }

  Iterable<Dish> dishesWithIngredients(Set<String> ingredients) {
    return dishes.where((d) => d.containsAll(ingredients));
  }

  String toString() {
    return "Receipt(dishes: ${dishes})";
  }
}