WedX - журнал о программировании и компьютерных науках

Подмножества элементов списка в Haskell

Может ли кто-нибудь помочь мне создать все подмножества данного набора?

Пример: если у меня есть [2,3,4] и я хочу, чтобы K=2, это означает, что мне нужны пары из двух => [[2,3], [3,2], [2,4], [4]. ,2], [3,4], [4,3]]

Я написал этот код, но он генерирует только количество подмножеств:

arrange::Int->Int->Int
arrange n 1=n
arrange n r=n*arrange (n-1) (r-1)

Другая версия, но она не генерирует все решения подмножеств:

  arrange 0 _ =[[]]
  arrange _ []=[]
  arrange n (x:xs)=(map(x:)) (arrange (n-1) xs)++
                   (arrange n xs)
haskell
17.05.2015

  • Нет. Но если у вас есть идеи для моего примера, пожалуйста, помогите мне с реализацией. 17.05.2015
  • соответствующее имя является подмножеством, а не расположением списка. пожалуйста, обновите свой вопрос. Я добавил ответ на то, что вы ищете. 17.05.2015
  • @DeJaVo, нет, это тоже не подходящее имя. Подмножества предполагают, что порядок не имеет значения. Согласно Википедии, они называются частичными перестановками или, когда известны конкретные размеры, k-перестановками n (например, 2-перестановками 3). 17.05.2015

Ответы:


1

Ну, исходя из вашего примера, это возможное решение:

import Data.List (permutations)

pick :: Int -> [a] -> [[a]]
pick 0 _ = [[]]
pick _ [] = []
pick n (x:xs) = map (x:) (pick (n-1) xs) ++ pick n xs

arrange :: Int -> [a] -> [[a]]
arrange n = concatMap permutations . pick n

пример

λ> arrange 2 [2,3,4]
[[2,3],[3,2],[2,4],[4,2],[3,4],[4,3]]

как вы можете видеть, трюк заключается в том, чтобы просто выбрать несколько элементов, а затем получить все перестановки результатов (используя concatMap для объединения их вместе)

конечно, это может быть домашним заданием, поэтому вы можете реализовать permutations самостоятельно;)

17.05.2015
  • Я написал код для перестановок, но он все еще не работает. 'импортировать Data.List (удалить)' pick :: Int -> [a] -> [[a]] pick 0 _ = [[]] pick _ [] = [] pick n (x:xs) = map ( x:) (выбрать (n-1) xs) ++ выбрать n xs перестановок :: [a] -> [[a]] перестановок [] = [[]] перестановок xs = [ x:ys | x ‹- xs, ys ‹- перестановки (удалить x xs)] аранжировать :: Int -> [a] -> [[a]] аранжировать n = concatMap перестановки. выбрать н 17.05.2015
  • Я получаю эту ошибку: Файл ОШИБКИ: {Hugs}\An III\Haskell\aranj2.hs:10 - Невозможно обосновать ограничения в явно типизированной привязке *** Выражение: перестановки *** Тип: [a] -> [[a] ] *** Заданный контекст: () *** Ограничения: Eq a 17.05.2015
  • И если я изменю объявление перестановок с помощью этой одной перестановки :: Eq a =› [a] -> [[a]], я получаю эту ошибку: Невозможно обосновать ограничения в явно типизированной привязке *** Выражение: упорядочить *** Тип: Int -> [a] -> [[a]] *** Заданный контекст: () *** Ограничения: Eq a 17.05.2015
  • хорошо, используя delete, вы должны включать Eq a везде, где вы его используете (включая мой arrange), но есть способ (очевидный) написать permutations без удаления;) - но ваш в порядке - просто добавьте ограничения 17.05.2015
  • Спасибо за ваши указания. Это мне очень помогает. 17.05.2015
  • Рад, что смог помочь - если это отвечает на ваш вопрос, возможно, вы захотите его принять - если нет, я с радостью постараюсь помочь вам в дальнейшем. 17.05.2015
  • Не могли бы вы объяснить, что на самом деле делает функция выбора? 27.08.2017
  • @JavascriptLoser генерирует список способов выбрать n элементов из списка ввода (без изменения порядка) - например, pick 2 [1,2,3] = [[1,2],[1,3],[2,3]] 27.08.2017
    • Новые материалы
    Я хотел выучить язык программирования MVC4, но не мог выучить его раньше, потому что это выглядит сложно…
    Просто начните и учитесь самостоятельно Я хотел выучить язык программирования MVC4, но не мог выучить его раньше, потому что он кажется мне сложным, и я бросил его. Это в основном инструмент..
    Лицензии с открытым исходным кодом: руководство для разработчиков и создателей
    В динамичном мире разработки программного обеспечения открытый исходный код стал мощной парадигмой, способствующей сотрудничеству, инновациям и прогрессу, движимому сообществом. В основе..
    Объяснение документов 02: BERT
    BERT представил двухступенчатую структуру обучения: предварительное обучение и тонкая настройка. Во время предварительного обучения модель обучается на неразмеченных данных с помощью..
    Как проанализировать работу вашего классификатора?
    Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..
    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..
    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..
    Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter
    Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..
    Для любых предложений по сайту: [email protected]