def Fitch(rooted_tree):
    # using of Fitch algorithm 
    
    # traverse Tree in post-order
    for node in rooted_tree.traverse('postorder'):
        if not node.is_leaf():
            children = node.get_children()
            intersect = (children[0].data['split']).intersection(children[1].data['split'])
            if len(intersect) == 0:
                node.data['split'] = (children[0].data['split']).union(children[1].data['split'])
            else:
                node.data['split'] = intersect
    # traverse top-down 
    
    for node in rooted_tree.traverse('levelorder'):
        if node.is_root(): # for the root 
            # if the root has 2 candidatnode.add_features()e, randomly choose 1, and get the numeric value
            node.data['split'] = (random.sample(node.data['split'],1))[0] 
        else:
            # for children node, first check the data from the ancestor
            ancestors = node.get_ancestors() # get the list of ancestor
            data = ancestors[0].data['split'] # get the data from the parent
            if data in node.data['split']:# check if the node.data has value equal to its parent data
                node.data['split'] =data
            else:
                node.data['split'] = (random.sample(node.data['split'],1))[0]
    return rooted_tree

def convert(snippet, phrase):
	#snippet = question, phrase = answer
	class_names = [w.capitalize() for w in random.sample(WORDS, snippet.count("%%%"))]
	other_names = random.sample(WORDS, snippet.count("***"))
	results = []
	param_names = []
	
	for i in range(0, snippet.count("@@@")):
		param_count = random.randint(1,3)
		param_names.append(', '.join(random.sample(WORDS, param_count)))
	
	for sentence in snippet, phrase:
		# copy sentence in result
		result = sentence[:]
		
		# fake class names
		for word in class_names:
			result = result.replace("%%%", word, 1)
		
		# fake other names
		for word in other_names:
			result = result.replace("***", word, 1)
		
		# fake parameter lists
		for word in param_names:
			result = result.replace("@@@", word, 1)
			
		results.append(result)
	
	return results

def convert(snippet, phrase):
    class_names = [w.capitalize() for w in
               random.sample(WORDS, snippet.count("%%%"))]
    other_names = random.sample(WORDS, snippet.count("***"))
    results = []
    param_names = []

    for i in range(0, snippet.count("@@@")):
        param_count = random.randint(1,3)
        param_names.append(', '.join(random.sample(WORDS, param_count)))

    for sentence in snippet, phrase:
        result = sentence[:]

        for word in class_names:
            result = result.replace("%%%", word, 1)

        for word in other_names:
            result = result.replace("***", word, 1)

        for word in param_names:
            result = result.replace("@@@", word, 1)

        results.append(result)

    return results

def disturb(g,cl):
    ng=g.copy()
    ng.remove_edges_from(ng.edges())
    for i in range(len(cl)-1):#连接簇之间不变的线
        j=i+1
        while j<len(cl):
            for x in itertools.product(cl[i],cl[j]):#簇之间两两（cl[i],cl[j]）笛卡尔积
                if g.has_edge(x[0],x[1]):
                    ng.add_edge(x[0],x[1])
            j+=1
    sub=[]
    for i in range(len(cl)):#打乱簇内线
        sub=g.subgraph(cl[i])
        edges=sub.edges()
        numOfe=sub.number_of_edges()
        sub.remove_edges_from(edges)
        setE=[]
        tupleE=[]
        for k in range(numOfe):#生成numOfe条线
            l=set(random.sample(cl[i],2))#随机生成cl[i]内两个数，并生成集合，因为集合无序，容易判断该两个数是否已经生成了
            while l in setE:
                l=set(random.sample(cl[i],2))
            setE.append(l)
        
        for item in setE:#集合变元组，用来添加边
            tupleE.append(tuple(item))
        ng.add_edges_from(tupleE)
    return ng

def generateRandomInices(r, c, p, t):
	l = []
	while len(l) < p:
		randomIndex = (random.sample(range(r),1)[0], random.sample(range(c),1)[0])
		if randomIndex not in t and randomIndex not in l:
			l += [randomIndex]
	return l

def doge(phenny,input):
    text = input.groups()
    if not text[1]:
        phenny.reply('  no word       such fail             wow               bad say')
        return
    syn = get_from_thesaurus(text[1])
    if not syn:
        phenny.reply('  no word       such fail             wow               bad say')
        return
    syn = [(x.split())[0] for x in syn]
    syn = set(syn)
    n = min([random.randint(3,6), len(syn)])
    dog = random.sample(shibe,n)
    ss = random.sample(syn,n)
    out = []
    wow = 0
    for i in range(0,n):
        sp = [' ' for j in range(0,random.randint(5,20))]
        if not wow and random.randint(0,1):
            out.append(''.join(sp)+'wow')
            wow = 1
            i = i - 1
        else:
            out.append(''.join(sp)+dog[i]+ss[i])
    phenny.reply(' '.join(out))

def split_gtf(gtf, sample_size=None, out_dir=None):
    """
    split a GTF file into two equal parts, randomly selecting genes.
    sample_size will select up to sample_size genes in total
    """
    if out_dir:
        part1_fn = os.path.basename(os.path.splitext(gtf)[0]) + ".part1.gtf"
        part2_fn = os.path.basename(os.path.splitext(gtf)[0]) + ".part2.gtf"
        part1 = os.path.join(out_dir, part1_fn)
        part2 = os.path.join(out_dir, part2_fn)
        if file_exists(part1) and file_exists(part2):
            return part1, part2
    else:
        part1 = tempfile.NamedTemporaryFile(delete=False, suffix=".part1.gtf").name
        part2 = tempfile.NamedTemporaryFile(delete=False, suffix=".part2.gtf").name

    db = get_gtf_db(gtf)
    gene_ids = set([x['gene_id'][0] for x in db.all_features()])
    if not sample_size or (sample_size and sample_size > len(gene_ids)):
        sample_size = len(gene_ids)
    gene_ids = set(random.sample(gene_ids, sample_size))
    part1_ids = set(random.sample(gene_ids, sample_size / 2))
    part2_ids = gene_ids.difference(part1_ids)
    with open(part1, "w") as part1_handle:
        for gene in part1_ids:
            for feature in db.children(gene):
                part1_handle.write(str(feature) + "\n")
    with open(part2, "w") as part2_handle:
        for gene in part2_ids:
            for feature in db.children(gene):
                part2_handle.write(str(feature) + "\n")
    return part1, part2

def ReWeightedRW(G, incomes, sample_size):
	node = random.sample(G, 1)[0]

	sampling = list()
	node_degrees = list()
	node_incomes = list()

	for i in range(sample_size):
		sampling.append(node)
		node_degrees.append(len(G[node]))
		node_incomes.append(incomes[node])

		# select a random neighbor of node
		node = random.sample(G.get(node), 1)[0]

	# the normal random walk. biased, without correction.
	biased_average_degrees = numpy.average(node_degrees)
	biased_average_incomes = numpy.average(node_incomes)

	# correcting the random walk sampling with inversed-node-degree prob
	normalization_constant = 0.0
	for x in node_degrees:
		normalization_constant += (1.0 / x)

	prob = list()
	for x in node_degrees:
		temp = (1.0 / x) / normalization_constant
		prob.append(temp)

	reweighted_average_degrees = sum(i*j for i, j in zip(prob,node_degrees))
	reweighted_average_incomes = sum(i*j for i, j in zip(prob,node_incomes))
	
	return [biased_average_degrees, reweighted_average_degrees, biased_average_incomes, reweighted_average_incomes]

def convert(snippets,phrase):
    class_names=[w.capitalize() for w in random.sample(words,snippet.count("%%%"))]
    #print class_names
    other_names=random.sample(words,snippet.count("***"))
    #print other_names
    results=[]
    param_names=[]
    
    for i in range(0,snippet.count("@@@")):
        param_count=random.randint(1,3)
        param_names.append(','.join(random.sample(words,param_count)))
        #print param_names
        
    for sentence in [snippet, phrase]:
        #print sentence
        result=sentence[:]
        #print result
    #result=[snippet,phrase]     
        for word in class_names:
            result=result.replace('%%%',word,1)
            #print word
            #print result+"a class names"
        for word in other_names :
            result=result.replace("***",word,1)
            #print word
            #print result+"a other names"
        for word in param_names:
            result=result.replace("@@@",word,1)
            #print word
            #print result+"a param names"

        results.append(result)
    #print results
    #print result
    return results

    def __init__(self, n=1000, k=10, p=0.02947368):
        self.n = n
        self.k = k
        self.p = p
        self.ws = nx.watts_strogatz_graph(self.n, self.k, self.p, seed='nsll')
        nx.set_node_attributes(self.ws, 'SIR', 'S')
        self.clustering = nx.clustering(self.ws)
        self.betweenness = nx.betweenness_centrality(self.ws)
        p_r_0 = 0.001
        r_0 = int(self.n * p_r_0)
        if r_0 < 1:
            r_0 = 1
        random.seed('nsll')
        self.r = random.sample(self.ws.nodes(), r_0)

        i_0 = 4
        if i_0 < r_0:
            i_0 += 1
        random.seed('nsll')
        self.infected = random.sample(self.ws.nodes(), i_0)
        for n in self.infected:
            self.ws.node[n]['SIR'] = 'I'
        for n in self.r:
            self.ws.node[n]['SIR'] = 'R'
        self.s = self.n - len(self.infected) - len(self.r)
        print(self.r)
        print(self.infected)

    def pick_one(table):
        """Return one random element of a sequence or dict"""

        try:
            return table[random.sample(table.keys(), 1)[0]]
        except AttributeError:
            return random.sample(table, 1)[0]

def createCrossValidationFiles(n):
    # Make copies of the original positive and negative review files
    copyFile('hotelPosT-train.txt', 'postrain-reviews.txt')
    copyFile('hoteNegT-train.txt', 'negtrain-reviews.txt')
    
    # Read the positive and negative reviews into two separate lists
    posReviews = readFileIntoList('postrain-reviews.txt')
    negReviews = readFileIntoList('negtrain-reviews.txt')    
    
    # Use n random reviews for the positive review test set
    # Use the remaining reviews for the positive training set
    testPosReviews = random.sample(posReviews, n)
    trainingPosReviews = [review for review in posReviews if review not in testPosReviews]
    
    # Use n random reviews for the negative review test set
    # Use the remaining reviews for the negative training set
    testNegReviews = random.sample(negReviews, n)
    trainingNegReviews = [review for review in negReviews if review not in testNegReviews]
    
    # Write the test reviews to the test set file
    writeListToFile('test-reviews.txt', testPosReviews, False)
    writeListToFile('test-reviews.txt', testNegReviews, True)
    
    # Write the training reviews to the test set file
    writeListToFile('postrain-reviews.txt', trainingPosReviews, False)
    writeListToFile('negtrain-reviews.txt', trainingNegReviews, False) 

def convert(snippet, phrase):
    '''

    :param snippet:
    :param phrase:
    :return:
    '''
    class_names = [w.capitalize() for w in
                   random.sample(WORDS, snippet.count("%%%"))]
    other_names = random.sample(WORDS, snippet.count("***"))
    results = []
    param_names = []

    for i in range(0, snippet.count("@@@")):
        param_count = random.randint(1,3)
        param_names.append(', '.join(random.sample(WORDS, param_count)))

    for sentence in snippet, phrase:
        result = sentence[:]# result is a list. a copy of sentence

        # fake class names
        for word in class_names:
            result = result.replace("%%%", word, 1) #.replace replaces a string.

        # fake other names
        for word in other_names:
            result = result.replace("***", word, 1)

        # fake parameter lists
        for word in param_names:
            result = result.replace("@@@", word, 1)

        results.append(result)

    return results

    def change_to_Random_Dir(self):
        self.logger.debug("Current DIR: %s" % self.client.pwd())
        level1_dirs = []
        for file_name in self.client.nlst():
            try:
                self.client.cwd('/' + file_name)
                level1_dirs.append(file_name)
                self.logger.debug("Directory [L-1]: %s" % file_name)
            except ftplib.error_perm as detail:
                self.logger.debug("It's probably not a directory [L-1]: %s : %s" % (file_name, detail))
        self.logger.debug("Number of L1-Dirs: %i" % len(level1_dirs))

        randomly_sampled_L1_dir = random.sample(level1_dirs, 1)[0]
        self.client.cwd('/' + randomly_sampled_L1_dir)
        self.logger.debug("Current Level-1 DIR selected: %s" % self.client.pwd())

        level2_dirs = []
        for file_name_l2 in self.client.nlst():
            try:
                self.client.cwd('/' + randomly_sampled_L1_dir + '/' +file_name_l2)
                level2_dirs.append(file_name_l2)
                self.logger.debug("Directory [L-2]: %s" % file_name_l2)
            except ftplib.error_perm as detail:
                self.logger.debug("It's probably not a directory [L-2]: %s : %s" % (file_name_l2, detail))
        self.logger.debug("Number of L2-Dirs: %i" % len(level2_dirs))

        rand_L2_dir = random.sample(level2_dirs, 1)[0]
        self.client.cwd('/' + randomly_sampled_L1_dir + '/' + rand_L2_dir)
        self.logger.debug("Current Level-2 DIR selected: %s" % self.client.pwd())
        return self.client.pwd() + '/'

 def setUp(self):
     IMP.test.TestCase.setUp(self)
     self.numbers = random.sample(range(0, 1000), 100)
     self.keys = random.sample(range(0, 1000), 100)
     self.dictionary = dict()
     for key, val in zip(self.keys, self.numbers):
         self.dictionary[key] = val

def numberFactsLikeThis(klass, nf, rseed=None):
#    tolerances=[0.01, 0.025, 0.05, 0.1, 0.25, 0.5, 1.0, 2.5, 5.0, 10, 25, 50, 100]
    if rseed != None:
        seed(rseed)
    tolerances=[1.0, 2.5, 5.0, 10, 25, 50, 100]
    for tolerance in tolerances:
        ce=closeEnoughNumberFact(klass, nf.magnitude, nf.scale, tolerance, nf.measure)
        ce.remove(nf)
        candidates = []
        for nf_a in ce:
            duplicate = False
            for nf_b in candidates:
                if nf_b.value == nf_a.value:
                    duplicate = True
                    break
            if  not(duplicate):
                candidates.append(nf_a)    

        if len(candidates)>=4:
            bestTolerance = tolerance
            bestComparisons = sample(candidates[1:-1],2)
            bestComparisons.append(candidates[0])
            bestComparisons.append(candidates[-1])
            bestComparisons = sample(bestComparisons,4)
            break
        bestTolerance = tolerance
        bestComparisons = sample(candidates,len(candidates))
    score = round(1*log10(bestTolerance/1000)**2)*(len(bestComparisons)-1)
    return bestComparisons, bestTolerance, score

def sequential_rotor_estimation_cuda(reference_model_array, query_model_array, n_samples, n_objects_per_sample, mutation_probability=None):

    # Stack up a list of numbers
    total_matches = n_samples*n_objects_per_sample
    sample_indices = random.sample(range(total_matches), total_matches)

    n_mvs = reference_model_array.shape[0]
    sample_indices = [i%n_mvs for i in sample_indices]

    if mutation_probability is not None:
        reference_model_array_new = []
        mutation_flag = np.random.binomial(1,mutation_probability,total_matches)
        for mut, i in zip(mutation_flag, sample_indices):
            if mut:
                ref_ind = random.sample(range(len(reference_model_array)), 1)[0]
            else:
                ref_ind = i
            reference_model_array_new.append(reference_model_array[ref_ind,:])
        reference_model_array_new = np.array(reference_model_array_new)
    else:
        reference_model_array_new = np.array([reference_model_array[i,:] for i in sample_indices], dtype=np.float64)
    query_model_array_new = np.array([query_model_array[i, :] for i in sample_indices], dtype=np.float64)

    output = np.zeros((n_samples,32), dtype=np.float64)
    cost_array = np.zeros(n_samples, dtype=np.float64)

    blockdim = 64
    griddim = int(math.ceil(reference_model_array_new.shape[0] / blockdim))

    sequential_rotor_estimation_kernel[griddim, blockdim](reference_model_array_new, query_model_array_new, output, cost_array)

    return output, cost_array

    def cpl_2_change(self):
        """Change the playlist with random deletions, additions and reordering."""
        p_id = self.playlists['playlist to change'][-1]
        tracks = self.api.get_playlist_songs(p_id)

        #Apply random modifications.
        delete, add_dupe, add_blank, reorder = [random.choice([True, False]) for i in xrange(4)]

        if tracks and delete:
            log.debug("deleting tracks")
            track_is = range(len(tracks))
            #Select a random number of indices to delete.
            del_is = set(random.sample(track_is, random.choice(track_is)))
            tracks = [track for i, track in enumerate(tracks) if not i in del_is]

        if add_dupe:
            log.debug("adding dupe tracks from same playlist")
            tracks.extend(random.sample(tracks, random.randrange(len(tracks))))

        if add_blank:
            log.debug("adding random tracks with no eid")
            tracks.extend(random.sample(self.library, random.randrange(len(tracks))))

        if reorder:
            log.debug("shuffling tracks")
            random.shuffle(tracks)

        self.api.change_playlist(p_id, tracks)

        server_tracks = self.api.get_playlist_songs(p_id)

        self.assertEqual(len(tracks), len(server_tracks))

        for local_t, server_t in zip(tracks, server_tracks):
            self.assertEqual(local_t['id'], server_t['id'])

def create_sample_MAS_instance(node_count=100, optimum_lower_bound=0.8, density=0.4):
	"""
	Creates a directed graph, subject to the constraints:
		- Some solution must contain at at least (optimum_lower_bound)% of the edges.
		- The graph has density (density)
	"""
	
	# Create directed graph on nodes 1,...,node_count
	graph = networkx.DiGraph()
	graph.add_nodes_from(xrange(1, node_count+1))

	# Generate all possible directed edges, forward and backward
	possible_forward_edges = [(u,v) for u in graph.nodes_iter() for v in graph.nodes_iter() if u < v]
	possible_backward_edges = [(u,v) for u in graph.nodes_iter() for v in graph.nodes_iter() if u > v]

	# Compute balance of forward and backward edges
	edge_count = density * node_count * (node_count - 1) / 2
	
	# Sample subsets of forward and backward edges
	chosen_forward_edges = random.sample(possible_forward_edges, int(optimum_lower_bound * edge_count))
	chosen_backward_edges = random.sample(possible_backward_edges, int( (1 - optimum_lower_bound) * edge_count ))
	graph.add_edges_from(chosen_forward_edges)
	graph.add_edges_from(chosen_backward_edges)

	return permute_graph(graph)

def train_sample(feature_str, label, pos_train=0.5, neg_train=1000):
    """Perform training and testing using disjont samples from the full
    set of label_values. This is equivalent to doing one round of cross
    validation (see classipy.cross_validation) only it keeps the values around
    for display.

    Args:

    """
    all_hashes = list(cass.get_image_hashes())
    pos_hashes = [_[0] for _ in cass.buffered_get_row(cf_labels, label)]
    neg_hashes = list(set(all_hashes) - set(pos_hashes))

    if 0 < pos_train <= 1: pos_train = int(pos_train * len(pos_hashes))
    if 0 < neg_train <= 1: neg_train = int(neg_train * len(neg_hashes))

    # Choose a training sample and a testing sample
    if len(pos_hashes) < pos_train:
        raise ValueError('Not enough positive examples %s(%d)' % \
                         (label, len(pos_hashes)))
    if len(neg_hashes) < neg_train:
        raise ValueError('Not enough negative examples %s(%d)' % \
                         (label, len(neg_hashes)))

    pos_sample = random.sample(pos_hashes, pos_train)
    neg_sample = random.sample(neg_hashes, neg_train)

    labels = [-1 for _ in neg_sample] + [1 for _ in pos_sample]
    values = cass.get_feature_values(feature_str, neg_sample+pos_sample)

    global label_values
    label_values = zip(labels, values)

    print 'Training classifier with sample %d' % len(label_values)
    train_classifier(label_values)