def combination_calculator():
    """対話式組み合わせ計算機"""
    print("=== 組み合わせ・順列計算機 ===")
    
    while True:
        try:
            print("\n計算方法を選択してください:")
            print("1. 順列 (nPr)")
            print("2. 組み合わせ (nCr)")
            print("3. 終了")
            
            choice = input("選択 (1-3): ")
            
            if choice == '3':
                break
            elif choice in ['1', '2']:
                n = int(input("nの値を入力: "))
                r = int(input("rの値を入力: "))
                
                if choice == '1':
                    result = permutation_optimized(n, r)
                    print(f"{n}P{r} = {result:,}")
                else:
                    result = combination(n, r)
                    print(f"{n}C{r} = {result:,}")
                    
                # 実用例の提示
                if choice == '1':
                    print(f"例: {n}人から{r}つの順位を決める方法の数")
                else:
                    print(f"例: {n}人から{r}人のチームを選ぶ方法の数")
            else:
                print("無効な選択です。")
                
        except ValueError:
            print("有効な整数を入力してください。")
        except Exception as e:
            print(f"エラー: {e}")

# 実行してみましょう！
combination_calculator()

def pascal_visualizer():
    """パスカルの三角形の高度なビジュアライザー"""
    
    def highlight_patterns(triangle, pattern_type):
        """特定のパターンをハイライト"""
        patterns = {
            'even': lambda x: x % 2 == 0,      # 偶数
            'odd': lambda x: x % 2 == 1,       # 奇数
            'powers_of_2': lambda x: x & (x-1) == 0 and x > 0,  # 2の累乗
            'fibonacci': lambda x: is_fibonacci(x)  # フィボナッチ数
        }
        
        highlighted = []
        for row in triangle:
            highlighted_row = []
            for num in row:
                if patterns.get(pattern_type, lambda x: False)(num):
                    highlighted_row.append(f"[{num}]")
                else:
                    highlighted_row.append(str(num))
            highlighted.append(highlighted_row)
        
        return highlighted
    
    def is_fibonacci(n):
        """数がフィボナッチ数かどうか判定"""
        if n <= 0:
            return False
        
        # フィボナッチ数の判定：5n²±4のどちらかが完全平方数
        import math
        def is_perfect_square(x):
            root = int(math.sqrt(x))
            return root * root == x
        
        return is_perfect_square(5*n*n + 4) or is_perfect_square(5*n*n - 4)
    
    def print_highlighted_triangle(highlighted_triangle):
        """ハイライトされた三角形を表示"""
        max_width = len(' '.join(highlighted_triangle[-1]))
        
        for row in highlighted_triangle:
            row_str = ' '.join(row)
            padding = (max_width - len(row_str)) // 2
            print(' ' * padding + row_str)
    
    # メインプログラム
    rows = int(input("パスカルの三角形の行数を入力: "))
    triangle = generate_pascal_triangle(rows)
    
    print(f"\nパスカルの三角形 ({rows}行):")
    print_pascal_triangle(triangle)
    
    print("\nパターン解析:")
    patterns = ['even', 'odd', 'powers_of_2', 'fibonacci']
    
    for pattern in patterns:
        print(f"\n{pattern.replace('_', ' ').title()}のハイライト:")
        highlighted = highlight_patterns(triangle, pattern)
        print_highlighted_triangle(highlighted)

# 実行
pascal_visualizer()

def optimization_problems():
    """組み合わせ最適化の実践問題"""
    
    def knapsack_combinations(items, capacity):
        """ナップサック問題の組み合わせ論的アプローチ"""
        n = len(items)
        best_value = 0
        best_combination = []
        
        # 全ての組み合わせを試す（2^n通り）
        for i in range(1 << n):  # 2^n通りのビット表現
            current_weight = 0
            current_value = 0
            current_items = []
            
            for j in range(n):
                if i & (1 << j):  # j番目のアイテムを選択
                    current_weight += items[j][1]  # 重さ
                    current_value += items[j][2]   # 価値
                    current_items.append(items[j][0])  # 名前
            
            if current_weight <= capacity and current_value > best_value:
                best_value = current_value
                best_combination = current_items[:]
        
        return best_value, best_combination
    
    def schedule_combinations(tasks, time_limit):
        """タスクスケジューリング問題"""
        from itertools import combinations
        
        n = len(tasks)
        best_score = 0
        best_schedule = []
        
        # 全ての組み合わせを試す
        for r in range(1, n + 1):
            for combo in combinations(tasks, r):
                total_time = sum(task[1] for task in combo)
                total_score = sum(task[2] for task in combo)
                
                if total_time <= time_limit and total_score > best_score:
                    best_score = total_score
                    best_schedule = [task[0] for task in combo]
        
        return best_score, best_schedule
    
    # 問題1: ナップサック問題
    print("=== ナップサック問題 ===")
    items = [
        ("ノートPC", 2, 1000),     # (名前, 重さ, 価値)
        ("タブレット", 1, 500),
        ("本", 1, 200),
        ("カメラ", 3, 800),
        ("充電器", 1, 300)
    ]
    capacity = 5
    
    value, combination = knapsack_combinations(items, capacity)
    print(f"容量{capacity}kgの最適解:")
    print(f"選択アイテム: {combination}")
    print(f"総価値: {value}")
    
    print(f"\n全組み合わせ数: 2^{len(items)} = {2**len(items)}通り")
    
    # 問題2: タスクスケジューリング
    print("\n=== タスクスケジューリング問題 ===")
    tasks = [
        ("プレゼン準備", 3, 10),   # (タスク名, 時間, 重要度)
        ("レポート作成", 4, 8),
        ("会議参加", 2, 6),
        ("メール返信", 1, 4),
        ("資料読み込み", 2, 5)
    ]
    time_limit = 8
    
    score, schedule = schedule_combinations(tasks, time_limit)
    print(f"制限時間{time_limit}時間の最適スケジュール:")
    print(f"選択タスク: {schedule}")
    print(f"総重要度: {score}")
    
    total_combinations = sum(combination(len(tasks), r) for r in range(1, len(tasks)+1))
    print(f"\n全組み合わせ数: {total_combinations}通り")

# 実行
optimization_problems()