Add items to set inside a function call?

user_5930480 0
Viewed 374

I would like to better understand how we can add an item to a set as part of a function call, for example.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        result = []
        self.backtrack(nums, result, [], set()) 
        return result
    
    def backtrack(self, nums, result, perm, visited):
        
        if len(perm) == len(nums):
            result.append(perm)
        
        for num in nums:
            if num not in visited:
                visited.add(num)
                self.backtrack(nums, result, perm+[num], visited)
                visited.remove(num)

Looking at the for loop we can see that num is added to the array inside the backtrack function call, similarly if perm was a string then the code would look like,

backtrack(num, result, perm + str(num), visited)

This seems to suggest to me that when we want to add an item inside a function call their type must match, which is why adding num without the list cast would fail when perm is a list.

backtrack(num, result, perm + num, visited) # Fails

So then with that, is it possible to do the same for a set ? I tried

backtrack(num, result, perm + [num], visited + set(num))
backtrack(num, result, perm + str(num), visite + (num))

but both failed, seeing as an array and a set are both objects it seems strange to me that only 1 supports adding like so.

Could someone shed some light please !

Thank you

set python-3.x list function python
2 Answers

This seems to suggest to me that when we want to add an item inside a function call their type must match, which is why adding num without the list cast would fail when perm is a list.

  1. "Inside a function call" has absolutely nothing to do with it. Operators work the same way everywhere they are used.

  2. For + to work, the types on either side of the + sign have to support the operation. That's all there is to it. You can define + for your own classes to add unlike types together. (You probably shouldn't.)

  3. Casting is not a thing in Python. The [] is creating a list, that has one element: the existing value named num.

So then with that, is it possible to do the same for a set ?

No. The set type does not support the operator at all. You can test this directly:

>>> help(set.__add__)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: type object 'set' has no attribute '__add__'

This does allow other types to define + such that you can add a set to them; however, list explicitly disallows this, just as it's not allowed to "add" lists and tuples together (this decision is made because it's not clear what the result type should be).

seeing as an array and a set are both objects

This does not matter and is not interesting. Yes, a list (array means something different in Python and is not built-in) is an object. So is a set. So is a string. So is a function. So is the class Solution itself, as well as instances of that class. In Python, we take "everything is an object" quite seriously.

would like to better understand how we can add an item to a set

For this purpose, we have an explicit named method: .add. We can also use the operator | to combine two sets, as helpfully pointed out by @DavidWierichs (I need more caffeine). Combining two sets is conceptually a different operation - a set union rather than concatenation (you don't preserve the invariant that the combined len equals the sum of the original lens; and you don't preserve order, since conceptually there is no order to preserve in the first place) - so a different operator was chosen.

user_5236120

Adding type annotations to everything so you can run a type checker makes the failures a lot easier to interpret, since mypy will tell you exactly what type is expected for each operation and how that doesn't match what you provided. I annotated backtrack as follows:

def backtrack(
    nums: List[int],
    result: List[List[int]],
    perm: List[int],
    visited: Set[int]
) -> None:

Now if I try the lines of code in your question and run mypy I get useful error messages explaining why each is wrong (many of the failures are due to unrelated typos, e.g. using num instead of nums and visite instead of visited):

backtrack(num, result, perm + num, visited) # Fails
    error: Argument 1 to "backtrack" has incompatible type "int"; expected "List[int]"
    error: Unsupported operand types for + ("List[int]" and "int")

backtrack(num, result, perm + [num], visited + set(num))
    error: Argument 1 to "backtrack" has incompatible type "int"; expected "List[int]"
    error: Unsupported left operand type for + ("Set[int]")
    error: Argument 1 to "set" has incompatible type "int"; expected "Iterable[<nothing>]"

backtrack(num, result, perm + str(num), visite + (num))
    error: Argument 1 to "backtrack" has incompatible type "int"; expected "List[int]"
    error: Unsupported operand types for + ("List[int]" and "str")
    error: Name 'visite' is not defined

The set/list addition operators work the same way regardless of whether they happen as part of a function argument. As the error message Unsupported left operand type for + ("Set[int]") indicates, you can't add (+) two sets. Instead you union (|) them:

backtrack(nums, result, perm + [num], visited | set([num]))  # no errors!
user_37997590
Related