조금 전에 유행한, 인구가 약 절반이 되도록(듯이) 도도부현을 2분할하는 문제를 Mathematica 로 써 보았습니다.

버전은 Mathematica 11.0.1.0을 사용했습니다.

참고: 인구가 절반이 되도록 도도부현을 2분할해본 정리 - Togetter 정리

거지! Mathematica 문법 색칠!

이야기가 있지만 Mathematica Advent Calendar 2016 - Qiita,

"꼭 이 캘린더를 북돋워서 이번이야말로 Qiita에게 Mathematica의 신택스 하이라이트를 대응해 봅시다!"

이 1문에 「타었다!」라고 생각했습니다.

코드

Mathematica의 프로그램은 이것입니다. prefectureName 곳을 좋아하는 도도부현으로 다시 쓰고 놀아보세요. 히로시마 대학의 학생 등, Mathematica를 캠퍼스 라이센스로 마음껏 놀 수 있는 사람은 학생 중에 이 매우 비싼 소프트웨어로 놀아 보는 것도 좋을지도 모르겠네요. :-P

prefectureName = "Hiroshima";
a = CityData[{All, prefectureName, "Japan"}]
allPopulation = 
 Total[QuantityMagnitude[CityData[#, "Population"]] & /@ 
   a]; diff = 1;
Do[
 rs = RandomSample[Range[Length[a]], RandomInteger[Length[a]]];
 t = Total[
   QuantityMagnitude[CityData[#, "Population"]] & /@ a[[rs]]];
 d = Abs[1/2 - t/allPopulation];
 If[d < diff, diff = d; goodPartition = rs;];
 , {300}]
part = ImportString[URLFetch[#], 
     "JSON"] & /@ \
("http://nominatim.openstreetmap.org/search/?country=Japan&state=" <> 
        prefectureName <> "&city=" <> # <> 
        "&format=json&polygon_geojson=1" //. 
       x : {__Rule} :> Association[x] & /@ 
     Table[CityData[c, "Name"], {c, a[[goodPartition]]}]);
wholeArea = 
  "coordinates" /. ("geojson" /. 
     Import["http://nominatim.openstreetmap.org/search/?country=Japan&\
state=" <> prefectureName <> "&format=json&polygon_geojson=1", 
       "JSON"][[1]]);
Lookup[#, "display_name", {}] & /@ part
Lookup[#, "coordinates", {}] & /@ (Lookup[#, "geojson", {}] & /@ part);
GeoGraphics[{{EdgeForm[Red], FaceForm[Red], 
   Polygon /@ Flatten[%, 2]}, {EdgeForm[{Thick, Black}], 
   FaceForm[White], Polygon /@ wholeArea}}]

t = Total[
   QuantityMagnitude[CityData[#, "Population"]] & /@ 
    a[[goodPartition]]];

Print["Partition A: ", a[[goodPartition]], " ", t, " people (", 
 N[100 t/allPopulation], "%)"]

Print["Partition B: ", 
 a[[Complement[Range[Length[a]], goodPartition]]], " ", 
 allPopulation - t, " people (", N[100 (1 - t/allPopulation)], "%)"]

이번 알고리즘

분할 알고리즘

이번은 이 2분할 알고리즘에는, 사고 정지 알고리즘 난택 알고리즘으로 했습니다. (시간이 있으면 더 멋진 구축적인 알고리즘에도 도전하고 싶은 데스!)

분할 알고리즘 자체는 여기뿐입니다. ( 나머지 코드는 결과 그리기 때문입니다.)

Do[
 rs = RandomSample[Range[Length[a]], RandomInteger[Length[a]]];
 t = Total[
   QuantityMagnitude[CityData[#, "Population"]] & /@ a[[rs]]];
 d = Abs[1/2 - t/allPopulation];
 If[d < diff, diff = d; goodPartition = rs;];
 , {300}]

여기를 통과한 후에는 a[[goodPartition]] 가 「거의 2 분할한 한쪽의 시정촌 오브젝트의 리스트」가 되어 있습니다.

Mathematica는 이러한 지리적 정보도 네트워크를 통해 다운로드해 와서 순수 수학 이외에도 상당히 사용할 수 있습니다. 인구는 CityData[, "Population"]에서 취할 수 있습니다.

실험한 느낌에 따르면 200회에서 300회 정도 돌리면 거의 1%도 다르지 않는 선택을 얻을 수 있는 것 같습니다.

결과를 지도로 내보내는 곳은 OpenStreetMap

결과를 지도로 내보내는 곳까지 Mathematica에서 하고 싶었습니다만, Mathematica의 CityData[]가 일본의 시정촌의 경계를 내주지 않은 것 같기 때문에, 어쩔 수 없이 OpenStreetMap를 이용했습니다.

h tp : / / Minachi m. 오 스테레 t 마 p. 오 rg/세아 rch/? 이런 트리 = 자판 & s 갓 = 히로시마 & 시 ty = 히가시 히로시마 & 후 r 마 t = j 쏘 & 포 ly gon _ 게오 j 씨 = 1

에 액세스하면 히로시마현 히가시히로시마시의 정보를 GEO JSON 형식으로 주시기 때문에, 그것을 그대로 Polygon[]에 돌진하고 있을 뿐입니다.

OpenStreetMap Nominantim API에 대한 자세한 내용은 OpenStreetMap Nominatim: Search을 참조하십시오.

다양한 결과

일부 이미지로 결과를 올려 둡니다. 변수prefectureName를 원하는 도도부현으로 변경하여 놀아보세요.

히로시마현

오카야마현

야마구치현

오사카부

나가노현

아키타현

가나가와현

도쿄도

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

요약

그런 이유로 Qiita의 여러분, Qiita에 Mathematica의 신택스 하이라이트 대응해주세요! 🙇🏽