配列要素の比較

[マコトスパルビエロ]

遺伝的アルゴリズムを使って最適配置を探すプログラムをC++にて作ろうとしています。
質問自体は遺伝的アルゴリズムの本質からは離れます。

評価配列double V[N]の要素の値を比較して、その値が小さいものから、順番にＥ個分の添え字を取り出したいと考えています。

例えば、N=5、E=2とすると
V[5]={1.7,2.5,3.4,10.5,8.1,2.0}
から、0と5を選んでほしいのです。

コード:

for(i=0;i<N;i++){
       if(V[i]<temp){
	temp=V[i];
	}
}

上記のような方法で最小値や、その添え字を選ばせることはできます。
ただ、じゃあ2番目に小さい値はどこ？3番目は？で困っています。

2週間ほど前にもお世話になりました。
その時のプログラムは、おかげさまでほぼ完成することができました。
ところが、挙動に不満点があり、改良をしています。
時間がある時にお力をお貸しください。よろしくお願いします。

[jay]

こんな感じでどうでしょう？

コード:

#define NUM 2	//取得する数値の個数

int temp[NUM];	//取得した数値
int sr;

//検索する個数分ループさせる
for(int n=0; n<NUM; n++)
{
	sr=0;
	temp[n] = 1000000;

	//配列から数値を検索
	for(int i=0; i<N; i++)
	{
		//既に取得した値と比較する
		for(int s=0; s<n; s++)
		{
			if(V[s]==temp[n])
			{
				//同じ数値があれば既に取得されたということ
				sr = 1;
			}
		}
		//temp[n]よりより小さく、まだ取得されていなければ数値をtemp[n]に保管
		if(V[i]<temp[n] && sr==0)
		{
			temp[n]=V[i];
		}
	}
}

追記：
＞マコトスパルビエロさん
３つめのfor文のn++の部分はミスですね、これは失礼(一応訂正しておきました)
よく読んでなくてこちらも失礼しましたが、取得する必要があるのは添え字との事ですね
このコードの応用でそれも可能です、と言うか修正コードを載せるまでもなくそれは出来たみたいですね

何はともあれお役に立てたようで良かったです

[マコトスパルビエロ]

jay様
丁寧にコードまでありがとうございます！
書いていただいたコードのn++をs++に置き換えれば理解できたと思います。
要するに、一時に保存しておいた最小値と比較して同じものなら、採用しないと。
それなら、次々と検出できそうですね！
わかりやすい説明まで書いていただき、本当にありがとうございます。
とても素早い返信で感謝しています。

[かずま]

解決したのなら、そのコードを提示してほしいものです。
取り出したいのは添え字ではないのですか？
jay さんのプログラムは、かなり改変しないとダメな気がします。

C++ なら map に放り込めば、ソートが完了します。

コード:

#include <iostream>
#include <map>

int main()
{
    const int N = 6, E = 3;
    double V[N] = { 1.7, 2.5, 3.4, 10.5, 8.1, 2.0 };

    typedef std::map<double, int> Map;
    Map a;  
    for (int i = 0; i < N; i++) a[V[i]] = i;

    Map::iterator it = a.begin();
    for (int i = E; --i >= 0 && it != a.end(); ++it)
        std::cout << it->second << std::endl;
}    

[マコトスパルビエロ]

かずま様
解決後であるにもかかわらず返信ありがとうございます。
私はコードを丸パクリしたくないので、考え方を聞いて、それをもとにコードを書いてみようと思っています。
実際時間はかかるかもしれませんが、jayさんのやり方でできそうだと理解したので、解決！とさせていただきました。
添え字に関しては、最後のifの中で、求めている最小値を見つけた時に、iを他のところにストックしておけばいいと考えました。
ただ、そのコード自体はまだできてません。添え字部分は下記です。

コード:

if(V[i]<temp[n] && sr==0)
        {
            temp[n]=V[i];
soeji[n]=i;
        }

そして、かずま様のコードはとてもありがたいことに、このまま利用ができました。
非常にシンプルで簡潔なもので、素晴らしいです。
ただ、私がC++にて作ろうとしているのですが、mapを勉強していません。
したがって、コードのトレースができません。
この機会に勉強してみます。いい機会ですし、間違いなくこの機会に勉強すべきでしょう。
ありがとうございました！

[YuO]

1. 添字の配列等を作る
2. std::nth_element or std::partial_sortに，値を配列の添字とみなして，配列の値の比較を行うラムダ式等と共に放り込む

なんて方法も。

• std::nth_element
  上位N個が欲しい。N個の順序は問わない
• std::partial_sort
  上位N個が欲しい。N個も順序づけされていて欲しいが，残りは順序づけされている必要は無い
• std::sort, std::stable_sort
  全てを順序づけしたい

[かずま]

1. 添字の配列等を作る
2. std::nth_element or std::partial_sortに，値を配列の添字とみなして，配列の値の比較を行うラムダ式等と共に放り込む

なんて方法も。

なるほど、map より効率がよさそうですね。
ラムダ式の代わりに関数オブジェクトを使うと、

コード:

#include <iostream>
#include <algorithm>

class Comp {
    double *v;
public:
    Comp(double *x) : v(x) {}
    bool operator()(const int& a, const int & b) { return v[a] < v[b]; }
};

int main()
{
    const int N = 6, E = 3;
    double V[N] = { 1.7, 2.5, 3.4, 10.5, 8.1, 2.0 };

    int index[N];
    for (int i = 0; i < N; i++) index[i] = i;
    std::partial_sort(index, index + E, index + N, Comp(V));
 
    for (int i = 0; i < E; i++)  std::cout << index[i] << std::endl;
}