
"""simple docstring"""





from dataclasses import dataclass, field
from typing import Tuple

from ..utils import cached_property, is_torch_available, is_torch_tpu_available, logging, requires_backends
from .benchmark_args_utils import BenchmarkArguments


if is_torch_available():
				import torch

if is_torch_tpu_available(check_device=False):
				import torch_xla.core.xla_model as xm


_a														=		logging.get_logger(__name__)






@dataclass
class     _UpperCAmelCase(    lowerCamelCase	):
		lowercase__						=      [
		    'no_inference',
		    'no_cuda',
		    'no_tpu',
		    'no_speed',
		    'no_memory',
		    'no_env_print',
		    'no_multi_process',
		]



		def __init__(					self				,		**__a)       ->       Dict:






							'''simple docstring'''
							for deprecated_arg in self.deprecated_args:
												if deprecated_arg in kwargs:
																	_UpperCamelCase							 =  deprecated_arg[3:]
																	setattr(self				,		__a				,		not kwargs.pop(__a))
																	logger.warning(
																	    F'''{deprecated_arg} is depreciated. Please use --no_{positive_arg} or'''
																	    F''' {positive_arg}={kwargs[positive_arg]}''')

							_UpperCamelCase							 =  kwargs.pop('''torchscript'''				,		self.torchscript)
							_UpperCamelCase							 =  kwargs.pop('''torch_xla_tpu_print_metrics'''				,		self.torch_xla_tpu_print_metrics)
							_UpperCamelCase							 =  kwargs.pop('''fp16_opt_level'''				,		self.fpaa_opt_level)
							super().__init__(**__a)

		lowercase__						=      field(default=lowerCamelCase      ,     metadata={'help': 'Trace the models using torchscript'}	)
		lowercase__						=      field(default=lowerCamelCase      ,     metadata={'help': 'Print Xla/PyTorch tpu metrics'}	)
		lowercase__						=      field(
		    default='O1'      ,     metadata={
		        'help': (
		            'For fp16: Apex AMP optimization level selected in [\'O0\', \'O1\', \'O2\', and \'O3\']. '
		            'See details at https://nvidia.github.io/apex/amp.html'
		        )
		    }      ,     )



		@cached_property
		def 						UpperCAmelCase							(					self)       ->       Tuple["torch.device", int]:






							'''simple docstring'''
							requires_backends(self				,		['''torch'''])
							logger.info('''PyTorch: setting up devices''')
							if not self.cuda:
												_UpperCamelCase							 =  torch.device('''cpu''')
												_UpperCamelCase							 =  0
							elif is_torch_tpu_available():
												_UpperCamelCase							 =  xm.xla_device()
												_UpperCamelCase							 =  0
							else:
												_UpperCamelCase							 =  torch.device('''cuda''' if torch.cuda.is_available() else '''cpu''')
												_UpperCamelCase							 =  torch.cuda.device_count()
							return device, n_gpu



		@property
		def 						UpperCAmelCase							(					self)       ->       List[str]:






							'''simple docstring'''
							return is_torch_tpu_available() and self.tpu



		@property
		def 						UpperCAmelCase							(					self)       ->       int:






							'''simple docstring'''
							requires_backends(self				,		['''torch'''])
							# TODO(PVP): currently only single GPU is supported
							return torch.cuda.current_device()



		@property
		def 						UpperCAmelCase							(					self)       ->       "torch.device":






							'''simple docstring'''
							requires_backends(self				,		['''torch'''])
							return self._setup_devices[0]



		@property
		def 						UpperCAmelCase							(					self)       ->       str:






							'''simple docstring'''
							requires_backends(self				,		['''torch'''])
							return self._setup_devices[1]




		@property
		def 						UpperCAmelCase							(					self)       ->       List[str]:






							'''simple docstring'''
							return self.n_gpu > 0








"""simple docstring"""





from collections import defaultdict






class     _UpperCAmelCase:



		def __init__(					self				,		__a				,		__a)       ->       Union[str, Any]:






							'''simple docstring'''
							_UpperCamelCase							 =  total  # total no of tasks (N)

							# DP table will have a dimension of (2^M)*N
							# initially all values are set to -1
							_UpperCamelCase							 =  [
							    [-1 for i in range(total + 1)] for j in range(2 ** len(__a))
							]

							_UpperCamelCase							 =  defaultdict(__a)  # stores the list of persons for each task

							# final_mask is used to check if all persons are included by setting all bits
							# to 1
							_UpperCamelCase							 =  (1 << len(__a)) - 1



		def 						UpperCAmelCase							(					self				,		__a				,		__a)       ->       Dict:






							'''simple docstring'''
							# if mask == self.finalmask all persons are distributed tasks, return 1
							if mask == self.final_mask:
												return 1

							# if not everyone gets the task and no more tasks are available, return 0
							if task_no > self.total_tasks:
												return 0

							# if case already considered
							if self.dp[mask][task_no] != -1:
												return self.dp[mask][task_no]

							# Number of ways when we don't this task in the arrangement
							_UpperCamelCase							 =  self.count_ways_until(__a				,		task_no + 1)

							# now assign the tasks one by one to all possible persons and recursively
							# assign for the remaining tasks.
							if task_no in self.task:
												for p in self.task[task_no]:
																	# if p is already given a task
																	if mask & (1 << p):
																						continue

																	# assign this task to p and change the mask value. And recursively
																	# assign tasks with the new mask value.
																	total_ways_util += self.count_ways_until(mask | (1 << p)				,		task_no + 1)

        # save the value.
							_UpperCamelCase							 =  total_ways_util

							return self.dp[mask][task_no]




		def 						UpperCAmelCase							(					self				,		__a)       ->       int:






							'''simple docstring'''
							# Store the list of persons for each task
							for i in range(len(__a)):
												for j in task_performed[i]:
																	self.task[j].append(__a)

        # call the function to fill the DP table, final answer is stored in dp[0][1]
							return self.count_ways_until(0				,		1)


if __name__ == "__main__":
				_a														=		5  # total no of tasks (the value of N)

				# the list of tasks that can be done by M persons.
				_a														=		[[1, 3, 4], [1, 2, 5], [3, 4]]
				print(
				    AssignmentUsingBitmask(task_performed, total_tasks).count_no_of_ways(
				        task_performed
				    )
				)






