#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Jul  4 16:57:46 2022

@author: chomette
"""

#Pour tester

import random as rd

def aleatoire(n,p,q):
    l=[]
    for i in range(n):
        l.append(rd.randint(p,q))
    return l


#1.1

def est_positive(L):
    for x in L:
        if x<0:
            return False
    return True

def est_croissante(L):
    n=len(L)
    for i in range(n-1):
        if L[i]>L[i+1]:
            return False
    return True

#1.2
    
def appartient(x,L):
    n=len(L)
    for i in range(n):
        if L[i]==x:
            return True
    return False

#Complexité (au pire) en O(n) où n=len(L)
#En effet si x n'est pas dans L, on fait exactement n tests
#Dans le cas contraire on fait au plus n tests...



def appartient_liste_triee(x,L):
    n=len(L)
    if n==0:
        return False
    elif x==L[n//2]:
        return True
    elif x<L[n//2]:
        return appartient_liste_triee(x,L[:n//2])
    else:
        return appartient_liste_triee(x,L[n//2+1:])
     
#version iterative            
def appartient_liste_triee_bis(x,L):
    g,d=0,len(L)-1
    while g<=d:
        i=(g+d)//2
        if x==L[i]:
            return True
        elif x<L[i]:
            d=i-1
        else:
            g=i+1
    return False
        
#Si 2^p<=n<2^(p+1), on a au plus p+1 étapes, 
#la taille de la liste étant divisée par 2 à chaque étape
#Or p est la partie entière de log_2(n), 
#d'où une complexité en O(ln n)
       
        
#2.1
            
def minimum(L):
    n=len(L)
    indice,valeur=0,L[0]
    for i in range(1,n):
        if L[i]<valeur:
            indice,valeur=i,L[i]
    return indice,valeur
    

#2.2

def element_numero(k,L):
    assert k<=len(L)
    n=len(L)
    x=L[0]
    Linf,Lsup=[],[]
    for i in range(1,n):
        if L[i]<x:
            Linf.append(L[i])
        else:
            Lsup.append(L[i])
    m=len(Linf)
    if m>=k:
        return element_numero(k,Linf)
    elif m==k-1:
        return x
    else:
        return element_numero(k-m-1,Lsup)
 
def mediane(L):
    n=len(L)
    return element_numero(n//2,L)

#3.1
            
def couples(L):
    liste_couples=[]
    n=len(L)
    for i in range(n-1):
        for j in range(i+1,n):
            liste_couples.append((L[i],L[j]))
    return liste_couples

def triplets(L):
    liste_triplets=[]
    n=len(L)
    for i in range(n-2):
        for j in range(i+1,n-1):
            for k in range(j+1,n):
                liste_triplets.append((L[i],L[j],L[k]))
    return liste_triplets

#3.2

def binaire(k,n):
    assert k<2**n
    l=[]
    for i in range(n):
        l.append(k%2)
        k=k//2
    return l

def binairebis(k,n):
    assert k<2**n
    l=[]
    for i in range(n):
        l.append(k//2**(n-1-i))
        k=k%(2**(n-1-i))
    return l

#Dans cette version, les chiffres en base 2 sont rangés à l'envers...

def parties(L):
    n=len(L)
    liste_parties=[]
    for k in range(2**n):
        listebinaire=binaire(k,n)
        partie=[L[i] for i in range(n) if listebinaire[i]==1]
        liste_parties.append(partie)
    return liste_parties

#3.3
    
import numpy as np

def triangle_pascal(n,p):
    T=np.zeros((n+1,p+1),dtype=int)
    T[0,0]=1
    for k in range(1,n+1):
        T[k,0]=1
        for i in range(1,p+1):
            T[k,i]=T[k-1,i-1]+T[k-1,i]
    return T

def partie_k_elements_numero(i,k,n):
    T=triangle_pascal(n,k)
    assert i<T[n,k]
    liste=[]
    while k>0:
        if i>=T[n-1,k]:
            liste.insert(0,n-1)
            i-=T[n-1,k]
            k-=1
            n-=1
        else:
            n-=1
    return liste

def parties_k_elements(k,L):
    n=len(L)
    p=triangle_pascal(n,k)[n,k]
    liste_parties=[]
    for i in range(p):
        liste_parties.append([L[j] for j in partie_k_elements_numero(i,k,n)])
    return liste_parties