楼主: Nicolle
659 32

【Python Package】Abstract Data Structures and Algorithms-Python [推广有奖]

版主

巨擘

0%

还不是VIP/贵宾

-

TA的文库  其他...

Python Programming

SAS Programming

Structural Equation Modeling

威望
16
论坛币
12315348 个
学术水平
2826 点
热心指数
2802 点
信用等级
2629 点
经验
430640 点
帖子
18465
精华
81
在线时间
6988 小时
注册时间
2005-4-23
最后登录
2018-10-22

Nicolle 学生认证  发表于 2018-2-14 10:56:32 |显示全部楼层
本帖最后由 Nicolle 于 2018-2-14 10:57 编辑

Abstract Data Structures and Algorithms-Python

The repository contains implementations for some of the most famous data structures, algorithms and applications of those algorithms

Installation:

Please use 'pip install data-structures-and-algorithms'. Keep in mind that the Applications folder is not included in the PyPi repository, because it only contains examples of using the data structures and the algorithms.

Issues:

Please register any issues you find in the github repository so that they can be fixed as soon as possible.

Requirements:

There are no dependencies on external libraries. However, a Python 3.x version is required.


本帖隐藏的内容

Python-DataStructuresAndAlgorithms-master.zip (77.75 KB)



本帖被以下文库推荐

stata SPSS
军旗飞扬 发表于 2018-2-14 10:57:51 |显示全部楼层
谢谢分享
已有 1 人评分论坛币 收起 理由
Nicolle + 20 鼓励积极发帖讨论

总评分: 论坛币 + 20   查看全部评分

回复

使用道具 举报

Nicolle 学生认证  发表于 2018-2-14 10:58:27 |显示全部楼层
  1. Copyright 2017 Nikolay Stanchev

  2. Licensed under the Apache License, Version 2.0 (the "License");
  3. you may not use this file except in compliance with the License.
  4. You may obtain a copy of the License at

  5.     http://www.apache.org/licenses/LICENSE-2.0

  6. Unless required by applicable law or agreed to in writing, software
  7. distributed under the License is distributed on an "AS IS" BASIS,
  8. WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  9. See the License for the specific language governing permissions and
  10. limitations under the License.
  11. """

  12. # Implementation for many math related algorithms


  13. def fibonacci_generator(limit=None):
  14.     """
  15.     this method implements a generator for the fibonacci numbers
  16.     :param limit: a limit for the generator so that it knows when to stop generating (default None - no limit)
  17.     :return: a generator object which yields the sequence of the fibonacci number
  18.     """

  19.     a, b = 0, 1
  20.     yield a

  21.     while True:
  22.         if b <= limit:
  23.             yield b
  24.         else:
  25.             raise StopIteration
  26.         a, b = b, a+b
复制代码
回复

使用道具 举报

Nicolle 学生认证  发表于 2018-2-14 10:59:32 |显示全部楼层
  1. """
  2. Copyright 2017 Nikolay Stanchev

  3. Licensed under the Apache License, Version 2.0 (the "License");
  4. you may not use this file except in compliance with the License.
  5. You may obtain a copy of the License at

  6.     http://www.apache.org/licenses/LICENSE-2.0

  7. Unless required by applicable law or agreed to in writing, software
  8. distributed under the License is distributed on an "AS IS" BASIS,
  9. WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  10. See the License for the specific language governing permissions and
  11. limitations under the License.
  12. """

  13. from ADTs.AbstractDataStructures import Stack, Queue, Graph


  14. # Breadth-First-Search (BFS) algorithm for graph traversing
  15. # takes a function as argument and applies the function to every node
  16. # if the result of the function is different than None, it returns the result
  17. def breadth_first_search(graph, func, start_node=None, *args, **kwargs):
  18.     if type(graph) != Graph:
  19.         raise TypeError("The first argument of this function must be of type Graph.")

  20.     if not callable(func):
  21.         raise TypeError("The second argument of this function must be a function.")

  22.     if graph.is_empty():
  23.         raise ValueError("You cannot traverse an empty graph")

  24.     try:
  25.         if start_node is not None and start_node not in graph:
  26.             raise KeyError("The starting node argument must be a node from the graph argument.")
  27.     except TypeError as err:
  28.         raise err

  29.     queue = Queue(graph.type())

  30.     if start_node is None:
  31.         for node in graph:
  32.             queue.enqueue(node)
  33.             break
  34.     else:
  35.         queue.enqueue(start_node)

  36.     explored = set()

  37.     while not queue.is_empty():
  38.         node = queue.dequeue()
  39.         explored.add(node)

  40.         result = func(node, *args, **kwargs)
  41.         if result is not None:
  42.             return result

  43.         for edge_node in graph.edges_of(node):
  44.             if edge_node not in explored and edge_node not in queue:
  45.                 queue.enqueue(edge_node)


  46. # Breadth-First-Search (BFS) algorithm for graph traversing
  47. # it returns a list of nodes of the graph in the order they would be traversed using BFS
  48. def breadth_first_search_list(graph, start_node=None):
  49.     if type(graph) != Graph:
  50.         raise TypeError("The first argument of this function must be of type Graph.")

  51.     if graph.is_empty():
  52.         raise ValueError("You cannot traverse an empty graph")

  53.     try:
  54.         if start_node is not None and start_node not in graph:
  55.             raise KeyError("The starting node argument must be a node from the graph argument.")
  56.     except TypeError as err:
  57.         raise err

  58.     queue = Queue(graph.type())

  59.     if start_node is None:
  60.         for node in graph:
  61.             queue.enqueue(node)
  62.             break
  63.     else:
  64.         queue.enqueue(start_node)

  65.     explored = set()
  66.     result_nodes = []

  67.     while not queue.is_empty():
  68.         node = queue.dequeue()
  69.         explored.add(node)
  70.         result_nodes.append(node)

  71.         for edge_node in graph.edges_of(node):
  72.             if edge_node not in explored and edge_node not in queue:
  73.                 queue.enqueue(edge_node)

  74.     return result_nodes


  75. # Breadth-First-Search (BFS) algorithm for graph traversing
  76. # a generator function, which yields the nodes of the graph in the order of the bfs traversal
  77. def breadth_first_search_generator(graph, start_node=None):
  78.     if type(graph) != Graph:
  79.         raise TypeError("The first argument of this function must be of type Graph.")

  80.     if graph.is_empty():
  81.         raise ValueError("You cannot traverse an empty graph")

  82.     try:
  83.         if start_node is not None and start_node not in graph:
  84.             raise KeyError("The starting node argument must be a node from the graph argument.")
  85.     except TypeError as err:
  86.         raise err

  87.     queue = Queue(graph.type())

  88.     if start_node is None:
  89.         for node in graph:
  90.             queue.enqueue(node)
  91.             break
  92.     else:
  93.         queue.enqueue(start_node)

  94.     explored = set()

  95.     while not queue.is_empty():
  96.         node = queue.dequeue()
  97.         explored.add(node)
  98.         yield node

  99.         for edge_node in graph.edges_of(node):
  100.             if edge_node not in explored and edge_node not in queue:
  101.                 queue.enqueue(edge_node)


  102. # Depth-First-Search (DFS) algorithm for graph traversing
  103. # takes a function as argument and applies the function to every node
  104. # if the result of the function is different than None, it returns the result
  105. def depth_first_search(graph, func, start_node=None, *args, **kwargs):
  106.     if type(graph) != Graph:
  107.         raise TypeError("The first argument of this function must be of type Graph.")

  108.     if not callable(func):
  109.         raise TypeError("The second argument of this function must be a function.")

  110.     if graph.is_empty():
  111.         raise ValueError("You cannot traverse an empty graph")

  112.     try:
  113.         if start_node is not None and start_node not in graph:
  114.             raise KeyError("The starting node argument must be a node from the graph argument.")
  115.     except TypeError as err:
  116.         raise err

  117.     stack = Stack(graph.type())

  118.     if start_node is None:
  119.         for node in graph:
  120.             stack.push(node)
  121.             break
  122.     else:
  123.         stack.push(start_node)

  124.     explored = set()

  125.     while not stack.is_empty():
  126.         node = stack.pop()
  127.         explored.add(node)

  128.         result = func(node, *args, **kwargs)
  129.         if result is not None:
  130.             return result

  131.         for edge_node in graph.edges_of(node)[:: -1]:
  132.             if edge_node not in explored and edge_node not in stack:
  133.                 stack.push(edge_node)


  134. # Depth-First-Search (DFS) algorithm for graph traversing
  135. # it returns a list of nodes of the graph in the order they would be traversed using DFS
  136. def depth_first_search_list(graph, start_node=None):
  137.     if type(graph) != Graph:
  138.         raise TypeError("The first argument of this function must be of type Graph.")

  139.     if graph.is_empty():
  140.         raise ValueError("You cannot traverse an empty graph")

  141.     try:
  142.         if start_node is not None and start_node not in graph:
  143.             raise KeyError("The starting node argument must be a node from the graph argument.")
  144.     except TypeError as err:
  145.         raise err

  146.     stack = Stack(graph.type())

  147.     if start_node is None:
  148.         for node in graph:
  149.             stack.push(node)
  150.             break
  151.     else:
  152.         stack.push(start_node)

  153.     explored = set()
  154.     result_nodes = []

  155.     while not stack.is_empty():
  156.         node = stack.pop()
  157.         explored.add(node)
  158.         result_nodes.append(node)

  159.         for edge_node in graph.edges_of(node)[:: -1]:
  160.             if edge_node not in explored and edge_node not in stack:
  161.                 stack.push(edge_node)

  162.     return result_nodes


  163. # Depth-First-Search (DFS) algorithm for graph traversing
  164. # a generator function, which yields the nodes of the graph in the order of the dfs traversal
  165. def depth_first_search_generator(graph, start_node=None):
  166.     if type(graph) != Graph:
  167.         raise TypeError("The first argument of this function must be of type Graph.")

  168.     if graph.is_empty():
  169.         raise ValueError("You cannot traverse an empty graph")

  170.     try:
  171.         if start_node is not None and start_node not in graph:
  172.             raise KeyError("The starting node argument must be a node from the graph argument.")
  173.     except TypeError as err:
  174.         raise err

  175.     stack = Stack(graph.type())

  176.     if start_node is None:
  177.         for node in graph:
  178.             stack.push(node)
  179.             break
  180.     else:
  181.         stack.push(start_node)

  182.     explored = set()

  183.     while not stack.is_empty():
  184.         node = stack.pop()
  185.         explored.add(node)
  186.         yield node

  187.         for edge_node in graph.edges_of(node)[:: -1]:
  188.             if edge_node not in explored and edge_node not in stack:
  189.                 stack.push(edge_node)
复制代码
回复

使用道具 举报

Nicolle 学生认证  发表于 2018-2-14 11:00:49 |显示全部楼层
  1. """
  2. Copyright 2017 Nikolay Stanchev

  3. Licensed under the Apache License, Version 2.0 (the "License");
  4. you may not use this file except in compliance with the License.
  5. You may obtain a copy of the License at

  6.     http://www.apache.org/licenses/LICENSE-2.0

  7. Unless required by applicable law or agreed to in writing, software
  8. distributed under the License is distributed on an "AS IS" BASIS,
  9. WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  10. See the License for the specific language governing permissions and
  11. limitations under the License.
  12. """


  13. # Bubble Sort Algorithm
  14. def bubble_sort(elements):
  15.     swapped = True
  16.     # going through all elements until no swaps were made
  17.     while swapped:
  18.         swapped = False
  19.         for i in range(0, len(elements) - 1, 1):
  20.             # comparing adjacent elements
  21.             if elements[i] > elements[i+1]:
  22.                 # if the previous elements is bigger than the next element, shift their values
  23.                 value = elements[i+1]
  24.                 elements[i+1] = elements[i]
  25.                 elements[i] = value
  26.                 swapped = True
  27.     return elements


  28. # Insertion Sort Algorithm
  29. def insertion_sort(elements):
  30.     # going through all elements, except the first one, we assume it is ordered
  31.     for i in range(1, len(elements)):
  32.         j = i
  33.         # comparing each element with the previous ones and adjusting it's position
  34.         while j > 0 and elements[j] < elements[j-1]:
  35.             value = elements[j]
  36.             elements[j] = elements[j-1]
  37.             elements[j-1] = value
  38.             j -= 1
  39.     return elements


  40. # Selection Sort Algorithm
  41. def selection_sort(elements):
  42.     # going through all elements
  43.     for i in range(0, len(elements)):
  44.         # finding the minimum element
  45.         min_index = i
  46.         for j in range(i+1, len(elements)):
  47.             if elements[j] < elements[min_index]:
  48.                 min_index = j
  49.         # shifting the current element with the minimum element
  50.         value = elements[i]
  51.         elements[i] = elements[min_index]
  52.         elements[min_index] = value
  53.     return elements


  54. # Quick Sort Algorithm
  55. def quick_sort(elements):
  56.     # calling the helper method partition_quick_sort with left index the beginning of the collection and right
  57.     # index the end of the collection
  58.     return partition_quick_sort(elements, 0, len(elements)-1)


  59. # a helper method, which sorts a partition of elements
  60. def partition_quick_sort(elements, left_end_index, right_end_index):
  61.     if left_end_index < right_end_index:
  62.         # choosing the pivot the be the leftmost element of the partition
  63.         pivot = elements[left_end_index]
  64.         left_index = left_end_index + 1
  65.         right_index = right_end_index

  66.         # sorting the partition in such a way that all elements that are less than the pivot value are before it and
  67.         # all elements greater than the pivot value are after it
  68.         while True:
  69.             while left_index <= right_index and elements[left_index] <= pivot:
  70.                 left_index += 1

  71.             while right_index >= left_index and elements[right_index] >= pivot:
  72.                 right_index -= 1

  73.             if left_index > right_index:
  74.                 break
  75.             else:
  76.                 value = elements[left_index]
  77.                 elements[left_index] = elements[right_index]
  78.                 elements[right_index] = value

  79.         elements[left_end_index] = elements[right_index]
  80.         elements[right_index] = pivot

  81.         # separating the partition into smaller collections, asuming that the pivot is sorted;
  82.         # recursively calling the method to the smaller collections
  83.         partition_quick_sort(elements, left_end_index, right_index-1)
  84.         partition_quick_sort(elements, right_index+1, right_end_index)

  85.         return elements

  86.     else:
  87.         return elements


  88. # Merge Sort Algorithm
  89. def merge_sort(elements):
  90.     # if the list has no elements or just one element, return the list
  91.     if len(elements) == 1 or len(elements) == 0:
  92.         return elements
  93.     else:
  94.         # slicing the elements into halves
  95.         left_half = merge_sort(elements[: int(len(elements)/2): 1])
  96.         right_half = merge_sort(elements[int(len(elements)/2):: 1])

  97.         # merging the left and the right half
  98.         left_half_index = 0
  99.         right_half_index = 0
  100.         merged_list = []

  101.         # comparing elements from both halves, while one the indices reaches the end of the list
  102.         while left_half_index != len(left_half) and right_half_index != len(right_half):
  103.             # if the element from the left half is less the the element from the right half, append the left element to
  104.             # the merged sorted list and increment the left_half_index
  105.             if left_half[left_half_index] < right_half[right_half_index]:
  106.                 merged_list.append(left_half[left_half_index])
  107.                 left_half_index += 1

  108.             # else if the element from the left half is greater than the element from the right half, append the right
  109.             # element to the merged sorted list and increment the right_half_index
  110.             elif left_half[left_half_index] > right_half[right_half_index]:
  111.                 merged_list.append(right_half[right_half_index])
  112.                 right_half_index += 1

  113.             # else if the elements are equal, append both elements to the merged sorted list and increment both indices,
  114.             # keep in mind that some implementations append only one of the elements to avoid repetition in the list
  115.             else:
  116.                 merged_list.append(left_half[left_half_index])
  117.                 merged_list.append(right_half[right_half_index])
  118.                 left_half_index += 1
  119.                 right_half_index += 1

  120.         # a check if there are elements left in the left half that weren't appended; if there are, we append them all
  121.         while left_half_index != len(left_half):
  122.             merged_list.append(left_half[left_half_index])
  123.             left_half_index += 1

  124.         # a check if there are elements left in the right half that weren't appended; if there are, we append them all
  125.         while right_half_index != len(right_half):
  126.             merged_list.append(right_half[right_half_index])
  127.             right_half_index += 1

  128.         # returning the sorted merged_list
  129.         return merged_list
复制代码
回复

使用道具 举报

jinyizhe282 发表于 2018-2-14 11:13:55 |显示全部楼层
哈哈哈哈哈  
已有 1 人评分论坛币 收起 理由
Nicolle + 20 鼓励积极发帖讨论

总评分: 论坛币 + 20   查看全部评分

回复

使用道具 举报

myazure 发表于 2018-2-14 11:16:51 |显示全部楼层
谢谢分享~~~~
已有 1 人评分论坛币 收起 理由
Nicolle + 20 鼓励积极发帖讨论

总评分: 论坛币 + 20   查看全部评分

回复

使用道具 举报

life_life 发表于 2018-2-14 11:26:05 |显示全部楼层
看看 看看 ,,
已有 1 人评分论坛币 收起 理由
Nicolle + 20 鼓励积极发帖讨论

总评分: 论坛币 + 20   查看全部评分

回复

使用道具 举报

life_life 发表于 2018-2-14 11:26:08 |显示全部楼层
看看 看看 ,,
回复

使用道具 举报

fengyg 企业认证  发表于 2018-2-14 11:35:47 |显示全部楼层
kankan
已有 1 人评分论坛币 收起 理由
Nicolle + 20 鼓励积极发帖讨论

总评分: 论坛币 + 20   查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 我要注册

GMT+8, 2018-10-23 07:35