Алгоритмы в Python

Алгоритм подсчета результатов голосования

Список предпочтений - список строк, в котором каждая строка соответствует одному голосующему человеку и представляет собой набор вариантов, из которых производится выбор, составленный голосующим в порядке уменьшения его предпочтений. То есть, на первом месте находится вариант, который нравится голосующему больше всего. На втором месте - вариант, который голосующий выбрал бы, если бы первый вариант не принимал участие в голосовании и т.д.

Строка предпочтений может содержать не все варианты голосования. В этом случае считается, что за не перечисленные в строке варианты данный голосующий не готов голосовать ни в каком случае.

Процедура голосования, известная как "Система единственного передаваемого голоса"Описание процедуры:

1. Составляется список предпочтений, в котором каждый голосующий заполняет одну строку своим набором вариантов голосования в порядке уменьшения предпочтений

2. Вариант с наименьшим числом голосов за первое место исключается из наборов вариантов предпочтений всех голосующих, а оставшиеся варианты продвигаются "вперед" в каждом наборе вариантов, в котором присутствовал исключенный вариант. Если при этом в какой-то строке образуется пустой набор вариантов голосования (т.е. до исключения эта строка содержала только исключаемый вариант), то эта строка удаляется из списка предпочтений

3. Действие 2 повторяется до тех пор, пока не останется только один вариант голосования. Он и объявляется победителем голосования.

4. По результатам голосования определяется не только победитель голосования, но и формируется общественный порядок предпочтений (то есть, все варианты располагаются друг за другом от первого места до последнего). Для этого перечисляют варианты голосования в порядке, обратном тому, в каком они исключались (т. е. сначала идет победитель, затем вариант, который исключили последним,

и так далее, до первого исключенного варианта).

5. Может так оказаться, что на этапе 2 сразу несколько вариантов голосования наберут одно и то же наименьшее число голосов. В этом случае они все одновременно исключаются из вариантов предпочтений всех голосующих и занимают одно и то же место в общественном порядке предпочтений. То же, в частности, относится и к победителю голосования: может так оказаться, что победителем голосования будут сразу несколько вариантов голосования.

Постановка задачи

Требуется написать программу на языке Python (и загрузить ее в данное задание), которая по списку предпочтений вариантов голосования составит общественный порядок предпочтений вариантов голосования в соответствии с описанной выше процедурой подсчета результатов голосования (то есть, программа должна расположить варианты голосования по "занятым ими местам").

Описание входящих данных

Входящие данные находятся в файле input.csv, который должен находиться в той же папке, что и программа. Файл содержит строки. Каждая строка соответствует одному голосующему. В каждой строке файла через запятую перечисляются номера вариантов голосования в порядке уменьшения предпочтений данного голосующего (слева - направо). В одной строке могут быть перечислены не все участвующие в голосовании варианты, но хотя бы одно число обязательно есть.

Пример файла загружен в кампус ниже данного задания.

Описание результата работы программы

Результатом работы программы должен быть файл result.txt, в котором должна быть только одна строка. В строке должен содержаться построенный общественный порядок предпочтений вариантов голосования, который представляет собой последовательность номеров голосования, распределенных по занятым ими местам. В строке через запятую перечисляются номера вариантов голосования по убыванию занимаемого места. Если определенное место заняли сразу несколько вариантов голосования, то эти варианты помещаются в строку в квадратных скобках, при этом между собой они разделяются запятыми. Пример возможного общественного порядка предпочтений вариантов голосования:

4,9,5,2,[10,12],13,3,7,[1,8,9],11,14